当前位置：首页 > news >正文

【小白笔记】大数加法

news 2026/4/8 13:25:55

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

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

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

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

对齐：从两个字符串的末尾（个位）开始加。
进位 (carry)：如果相加结果≥10\ge 10≥10，记下进位，留到下一位使用。
补齐：如果一个数字比另一个短，短的部分补0。
最后进位：如果所有位都加完了，进位还剩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：

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

这种写法的好处

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

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

1. 拆解分析

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