大数字符串求和Python代码超时，求优化方案与替代思路

问题描述 #

给定两个仅包含0-9数字的整数字符串，返回它们之和的字符串表示，需支持百万位级别的大数（无法直接转换为int类型处理）。现有代码可通过所有测试用例，但存在执行超时问题，需优化建议及其他可行实现思路。

当前代码：

def sum_strings(x, y):
      
    if x == '' and y == '':
        return '0'
    
    if x == '0' and y == '0':
        return '0'
    
    if x == '' and y == '0' or x == '0' and y == '':
        return '0'
    
    listaX = list(x)
    listaY = list(y)

    if len(listaX) - len(listaY) > 0:       
        while len(listaY) < len(listaX):
            listaY.insert(0, '0')
    if len(listaY) - len(listaX) > 0:       
        while len(listaY) > len(listaX):
            listaX.insert(0, '0')

    for i in range(0, len(listaX)):        
        listaX[i] = int(listaX[i])
        listaY[i] = int(listaY[i])

    listaSomas = []
    quociente = 0

    for i in range(len(listaX) - 1, -1, -1):
        soma = listaX[i] + listaY[i] + quociente
        if soma > 9 and i > 0:
            quociente = soma // 10
            listaSomas.insert(0, soma % 10)
        elif soma > 9 and i == 0:
            quociente = soma // 10
            listaSomas.insert(0, soma % 10)
            listaSomas.insert(0, quociente)
        elif soma <= 9:
            listaSomas.insert(0, soma)
            quociente = 0
            
    if listaSomas[0] == 0:                  
        listaSomas.remove(listaSomas[0])
            
    for i in range(0, len(listaSomas)):
        listaSomas[i] = str(listaSomas[i])
    listaSomas = ''.join(listaSomas)
    
    return listaSomas

#MAIN
print(sum_strings('123', '456'))

性能瓶颈分析 #

1. 列表头部插入的高开销：listaSomas.insert(0, ...)是O(n)操作，百万级数据下会触发大量元素移动，时间复杂度直接升至O(n²)。
2. 低效的补零方式：通过while循环+insert(0, '0')补零，每次插入都是O(n)，多次操作后累积开销极大。
3. 冗余的前置判断：多个空字符串与'0'的判断分支可以合并，虽对性能影响较小，但增加代码复杂度。
4. 多次类型转换遍历：先转字符列表、再逐个转int、最后转回字符串，多轮遍历增加不必要的开销。

针对原代码的优化方案 #

核心优化点 #

• 替换头部插入为尾部追加+反转：将insert(0, ...)改为append(...)，最后反转列表，把O(n²)的插入操作降为O(n)。
• 高效补零：通过字符串拼接直接生成补零后的字符串，避免循环插入。
• 合并前置判断：简化空字符串与'0'的判断逻辑。
• 简化类型转换：在计算时按需转换字符为整数，减少中间列表操作。

优化后的代码 #

def sum_strings(x, y):
    # 处理空字符串或全0的情况
    x = x or '0'
    y = y or '0'
    if x == '0' and y == '0':
        return '0'
    
    len_x, len_y = len(x), len(y)
    # 补零，使两个字符串长度一致
    if len_x > len_y:
        y = '0' * (len_x - len_y) + y
    else:
        x = '0' * (len_y - len_x) + x
    
    carry = 0
    result = []
    # 从尾部开始逐位相加
    for a, b in zip(reversed(x), reversed(y)):
        total = int(a) + int(b) + carry
        carry = total // 10
        result.append(str(total % 10))
    
    # 处理最后剩余的进位
    if carry > 0:
        result.append(str(carry))
    
    # 反转结果并去除前导零（如果有的话）
    final = ''.join(reversed(result)).lstrip('0')
    # 防止全零被strip成空字符串
    return final if final else '0'

其他高效实现思路 #

思路1：生成器逐位处理 #

利用生成器从两个字符串末尾取数，处理进位，最后拼接结果，代码更简洁且高效：

def sum_strings(x, y):
    x = x[::-1] if x else '0'
    y = y[::-1] if y else '0'
    carry = 0
    result = []
    max_len = max(len(x), len(y))
    for i in range(max_len):
        digit_x = int(x[i]) if i < len(x) else 0
        digit_y = int(y[i]) if i < len(y) else 0
        total = digit_x + digit_y + carry
        carry = total // 10
        result.append(str(total % 10))
    if carry:
        result.append(str(carry))
    final = ''.join(reversed(result)).lstrip('0')
    return final or '0'

思路2：分块处理（适合超大规模数字） #

将大数分成固定长度的块（如每9位，对应Python中高效处理的小整数范围），逐块相加后处理进位，减少循环次数：

def sum_strings(x, y):
    chunk_size = 9
    # 反转字符串方便从低位取块
    x_rev = x[::-1]
    y_rev = y[::-1]
    carry = 0
    result_chunks = []
    
    max_chunks = max(len(x_rev) // chunk_size + 1, len(y_rev) // chunk_size + 1)
    
    for i in range(max_chunks):
        # 取出当前块的字符串，反转回原顺序后转int
        chunk_x = x_rev[i*chunk_size : (i+1)*chunk_size][::-1] or '0'
        chunk_y = y_rev[i*chunk_size : (i+1)*chunk_size][::-1] or '0'
        total = int(chunk_x) + int(chunk_y) + carry
        carry = total // (10**chunk_size)
        # 格式化块为固定长度，避免前导零丢失（最后一块不需要）
        if i < max_chunks - 1 or carry > 0:
            result_chunks.append(f"{total % (10**chunk_size):0{chunk_size}d}")
        else:
            result_chunks.append(str(total % (10**chunk_size)))
    
    # 拼接块并去除前导零
    final = ''.join(reversed(result_chunks)).lstrip('0')
    return final or '0'

思路3：利用Python内置大整数（特殊场景） #

Python的int支持任意精度，对于百万位字符串，直接转换相加的效率可能超出预期（需测试极端场景）：

def sum_strings(x, y):
    num_x = int(x) if x else 0
    num_y = int(y) if y else 0
    return str(num_x + num_y)

注：该方法代码极简，但对于超大规模（如千万位）字符串，转换int的开销可能高于手动逐位处理，需根据题目限制选择。

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