如何最快实现百万位大数相加？（运行时需小于4秒）

需求说明 #

实现两个百万位大数的快速相加，约束条件为 1 ≤ 𝐴 ≤ 𝐵 ≤ 10^1000000，要求运行时间小于4秒。

输入示例

1000211 1000299

输出示例

2000510

问题场景 #

我尝试了以下代码，但速度不达标：

x, y = input().split()
print(int(x) + int(y))

高效解决方案 #

直接用Python的int类型处理百万位大数时，字符串转整数的过程会产生额外开销，导致超时。我们可以手动模拟竖式加法，直接操作字符串来优化性能：

def add_large_numbers(a, b):
    # 确保a为较长的数字字符串，简化遍历逻辑
    if len(a) < len(b):
        a, b = b, a
    # 反转字符串，从低位（原字符串末尾）开始计算
    a_reversed = a[::-1]
    b_reversed = b[::-1]
    result_digits = []
    carry = 0

    # 逐位相加
    for i in range(len(a_reversed)):
        digit_a = int(a_reversed[i])
        digit_b = int(b_reversed[i]) if i < len(b_reversed) else 0
        total = digit_a + digit_b + carry
        carry = total // 10
        result_digits.append(str(total % 10))
    
    # 处理最后的进位
    if carry != 0:
        result_digits.append(str(carry))
    
    # 反转结果并拼接成最终字符串
    return ''.join(reversed(result_digits))

# 使用sys.stdin读取输入，比input()更适合大规模输入
import sys
x, y = sys.stdin.readline().split()
print(add_large_numbers(x, y))

优化点说明 #

• 避免整数转换开销：直接操作字符串，跳过百万位字符串转int的耗时过程
• 列表存储中间结果：列表的append操作是 amortized O(1)，远快于不可变字符串的频繁拼接（每次拼接都是O(n)复杂度）
• 快速读取输入：sys.stdin.readline()读取大输入的速度比input()更快，减少IO等待时间

内容的提问来源于stack exchange，提问作者Xampel