【小白笔记】大数加法

“大数加法”是面试和算法练习中非常经典的一道题（如 LeetCode 415）。它的核心矛盾在于：计算机的标准整数类型（如 64 位整型）有最大值限制，当数字超过几十位甚至上百位时，直接相加会溢出。

处理这个问题的通用方案是：模拟人类列竖式计算的过程。

1. 核心逻辑：从低位到高位

就像我们在纸上做加法一样：

1. 对齐：从两个字符串的末尾（个位）开始加。
2. 进位 (carry)：如果相加结果≥10\ge 10≥10，记下进位，留到下一位使用。
3. 补齐：如果一个数字比另一个短，短的部分补0。
4. 最后进位：如果所有位都加完了，进位还剩1，别忘了在最高位补个1。

2. 代码实现 (Python)

classSolution:defaddStrings(self,num1:str,num2:str)->str:# 指针分别指向两个字符串的末端i,j=len(num1)-1,len(num2)-1carry=0# 进位res=[]# 存储每一位的结果# 只要还有位没加完，或者还有进位没处理whilei>=0orj>=0orcarry:# 取出当前位的值，如果指针已经越界则补 0x=int(num1[i])ifi>=0else0y=int(num2[j])ifj>=0else0# 计算当前位的总和total=x+y+carry# 更新进位和当前位carry=total//10res.append(str(total%10))# 指针左移i-=1j-=1# 因为是从个位开始存的，最后需要翻转回来并拼接成字符串return"".join(res[::-1])

3. 关键点拆解

A. 为什么用res[::-1]？

我们在循环里是先算出“个位”，再算“十位”，存入列表的结果是["个", "十", "百"]。这和我们阅读数字的顺序是相反的，所以最后需要[::-1]（反转）一下。

B.while i >= 0 or j >= 0 or carry:

这个条件非常精妙：

• i >= 0 or j >= 0：保证了即使两个数字长度不等，也能把长的那个加完。
• or carry：处理最特殊的情况，比如99 + 1。当i和j都走完了，carry还是1，循环会多跑一次，把最高位的1加上去。

C.total // 10和total % 10

• total // 10：取商。如果是 13，商就是 1，作为进位。
• total % 10：取余。如果是 13，余数就是 3，作为当前位的结果。

4. 复杂度分析

• 时间复杂度：O(max(N,M))O(max(N, M))O(max(N,M))。N,MN, MN,M分别为两个数字的长度。我们需要遍历较长的那个数字。
• 空间复杂度：O(max(N,M))O(max(N, M))O(max(N,M))。我们需要一个列表来存放结果。

# 只要还有位没加完，或者还有进位没处理whilei>=0orj>=0orcarry:# 取出当前位的值，如果指针已经越界则补 0x=int(num1[i])ifi>=0else0y=int(num2[j])ifj>=0else0

在 Python 中，x = A if condition else B叫做条件表达式（也叫三元运算符）。如果你觉得它看起来太挤，完全可以用标准的if-else结构来替换。

写开后的代码（更易读版）

我们将这两个赋值动作拆解到循环内部：

whilei>=0orj>=0orcarry:# --- 处理 num1 的当前位 ---ifi>=0:x=int(num1[i])else:x=0# 如果 num1 已经遍历完了，就当它是 0# --- 处理 num2 的当前位 ---ifj>=0:y=int(num2[j])else:y=0# 如果 num2 已经遍历完了，就当它是 0# --- 后面的逻辑不变 ---total=x+y+carry carry=total//10res.append(str(total%10))i-=1j-=1

为什么我们要这么写？（补零逻辑）

这种写法是为了解决**“两个数字长度不一样”**的问题。

比如计算123 + 45：

1. 第一轮：i指向3，j指向5。x=3, y=5。
2. 第二轮：i指向2，j指向4。x=2, y=4。
3. 第三轮：i指向1，但j已经变成-1了（越界）。
   • 此时，如果没有else: y = 0这段代码，程序就会报错。
   • 有了这段代码，y就会自动补0。这就相当于你在纸上算：

     1 2 3 + 0 4 5 <-- 这里的0就是靠 else 分支补上的 ---------

这种写法的好处

1. 调试方便：如果你想看x或者y到底取到了什么值，你可以在if分支里打断点或加print。
2. 逻辑安全：它显式地处理了索引越界的情况，不会出现IndexError。

• int（num1[i]）：代码中将字符转换为整数的关键步骤。我们可以把它拆成三部分来理解：

1. 拆解分析

• num1[i]：
  • num1是一个字符串（比如"123"）。
  • i是当前的索引（下标）。
  • 所以num1[i]是从字符串中取出第i个位置的字符。比如num1[0]取出的是"1"（注意，此时它还是带引号的字符串，不能直接做加法）。
• int(...)：
  • 这是一个内置函数，负责强制类型转换。
  • 它把括号里的东西转成整数。比如把字符串"1"转成数字1。
• x = ...：
  • 把转换后的数字赋值给变量x，这样x就可以参与数学运算了。

2. 为什么要加int()？

在 Python 中，字符串和数字是两种完全不同的“物种”。

如果你直接把两个字符串相加，Python 会把它们拼接起来：

"1" + "2" = "12"（这显然不是我们要的加法结果）

如果你把字符串和数字相加，Python 会报错：

"1" + 2 = TypeError（因为系统不知道你是想拼接还是想求和）

所以，我们需要用int()把字符变成数字，才能进行真正的数学运算：

int("1") + int("2") = 3

3. 放到大数加法背景下

假设我们要算"98" + "7"：

1. 当i指向num1的末尾（字符"8"）时：
   • x = int(num1[i])得到x = 8。
2. 当j指向num2的末尾（字符"7"）时：
   • y = int(num2[j])得到y = 7。
3. 这时我们就可以算：8 + 7 = 15，然后处理进位。

4. 这种写法的一个“坑”

在实际运行这行代码之前，必须确保num1[i]确实是一个代表数字的字符（比如'0'-'9'）。

• 如果是int("a")，代码会报错：ValueError。
• 在大数加法里，因为我们已经用if i >= 0保证了索引有效，且题目保证输入是数字字符串，所以这么写是安全的。

你会发现：在很多涉及数字字符串处理的题目中（比如求和、乘法、有效数字判断），int(s[i])都是出镜率最高的一行代码。