如何实现字符串形式的大数相加？（LeetCode 415）

简化版

给两个用字符串表示的非负整数 num1、num2（可能很大，超出 long 范围），不能直接转数字，求它们的和（仍以字符串返回）。做法是模拟竖式加法：从两个字符串的末尾（个位）开始逐位相加，用一个变量 carry 记录进位，每位结果 (d1 + d2 + carry) % 10、进位 / 10，从低位到高位拼接，最后反转。用双指针从后往前走，短的那个补 0。

详细版

String addStrings(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry != 0) {           // 任一还有位、或有进位就继续
        int d1 = i >= 0 ? num1.charAt(i) - '0' : 0;    // 短串补 0
        int d2 = j >= 0 ? num2.charAt(j) - '0' : 0;
        int sum = d1 + d2 + carry;
        sb.append(sum % 10);                            // 当前位
        carry = sum / 10;                               // 进位
        i--; j--;
    }
    return sb.reverse().toString();                     // 从低位拼的，最后反转
}

从末尾开始：个位在字符串末尾，逐位往高位（往前）加。
carry 进位：每位 sum = d1+d2+carry，写 sum%10、进 sum/10。
循环条件含 carry != 0：最高位可能还有进位（如 99+1=100），别漏。
复杂度：O(max(m,n)) 时间。

完整版教学

一、为什么不能直接转数字

num1、num2 可能有几百上千位，远超 long（约 19 位）甚至 int 的范围。直接 Long.parseLong 会溢出。所以必须把它们当字符串，模拟人手算加法的竖式过程——一位一位加、处理进位。这是「大数运算」的基本功，加法、乘法（43 字符串相乘）、相减都是同一套模拟思路。

二、模拟竖式：从个位往高位加

回忆小学列竖式：数字右对齐，从个位（最右）开始，逐位相加，满 10 向前进 1。字符串里个位就是最后一个字符，所以：

用双指针 i、j 分别指向 num1、num2 的末尾，从后往前走。
每一步取两个当前位的数字（字符减 '0' 得数值），加上上一位的进位 carry。
当前位结果 = sum % 10，新进位 = sum / 10。
i--、j-- 移向更高位。

因为是从低位往高位算的，结果也是低位先产生，所以拼接后要反转才是正确顺序（或用头插）。

三、三个关键细节

① 短串补 0：两个数长度可能不同，短的那个高位不足时补 0（i >= 0 ? ... : 0）。这样不用先对齐补零，循环里自然处理。

② 循环条件要含 carry != 0：写成 while (i >= 0 || j >= 0) 会漏掉最高位的进位。例如 "99" + "1"：加完个位、十位后 carry=1，但两个指针都越界了，若不判 carry != 0 就丢了最前面的 1，结果错成 "00" 而非 "100"。所以条件必须是 i >= 0 || j >= 0 || carry != 0。

③ 最后反转：从个位开始 append，得到的是逆序，sb.reverse() 得到正确结果。

四、和相关大数题的联系

两数相加（链表版，2）：链表按位存数字，同样是「逐位加 + 进位」，只是数据结构换成链表，且链表通常已经是「低位在前」，不用反转。
字符串相乘（43）：大数乘法，用「逐位相乘累加到结果数组的对应位」+ 统一处理进位，比加法复杂一档，但内核还是模拟竖式。
二进制求和（67）：把 % 10 / 10 换成 % 2 / 2 就是二进制加法。

掌握本题的「双指针从后往前 + carry」模板，这一类都能套。

五、易错点

忘记 carry != 0 的循环条件 → 漏最高位进位（最经典错误）。
忘记反转 → 结果顺序反了。
字符转数字 → 用 charAt(i) - '0'，别忘减 '0'。
前导零：本题输入无前导零、结果也不会有（除非结果是 “0”），一般不用额外处理；若题目可能产生前导零要清理。

六、按竖式不变量处理不同长度

双指针从末尾出发，是因为十进制进位从低位流向高位。每轮消费两个字符串尚未处理的最低位，并把 sum%10 放入逆序结果；carry=sum/10 是唯一需要传给下一列的状态。短字符串耗尽后把缺失位当 0，不需要补齐字符串。

num1 =  987
num2 =   65
个位：7+5+0=12，写 2，carry=1
十位：8+6+1=15，写 5，carry=1
百位：9+0+1=10，写 0，carry=1
末尾补 carry=1，逆序缓冲为 2501
反转得到 1052

校验维度	本题必须保持的结论
循环/递推不变量	每轮后，缓冲区保存已处理低位的逆序正确数字，carry 只可能是 0 或 1。
边界条件	输入可能长度不同；循环条件必须包含 `carry!=0`，否则 `999+1` 会漏最高位。
复杂度与代价	时间 O(max(m,n))，结果缓冲 O(max(m,n))，不受机器整数范围限制。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：每轮后，缓冲区保存已处理低位的逆序正确数字，carry 只可能是 0 或 1。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“num1 = 987”开始手推，最后应得到“反转得到 1052”。
边界复核：输入可能长度不同；循环条件必须包含 carry!=0，否则 999+1 会漏最高位。
代价复核：时间 O(max(m,n))，结果缓冲 O(max(m,n))，不受机器整数范围限制。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“每轮后，缓冲区保存已处理低位的逆序正确数字，carry 只可能是 0 或 1。”这条正确性主线不能省。

八、常见误区与追问

误区：先把两个字符串转成 long 更简单且等价。 输入长度可能超过 long 范围，转换会溢出或直接失败。
误区：主循环只需在两个指针都未越界时执行。 应在任一数字还有位或仍有进位时继续。
误区：逐位 append 后无需反转。 从个位开始得到的是逆序数字，除非改为头插，否则必须最终反转。
追问：carry 为什么最多为 1？ 十进制下最大列和是 9+9+1=19，整除 10 只会得到 0 或 1。
追问：字符串乘法如何推广？ 每对数字相乘累加到对应位数组，再统一处理进位，类似手算乘法。
追问：能否原地写入输入字符串？ Java String 不可变，而且结果可能多一位，通常使用 StringBuilder。

九、加强记忆

字符串大数相加 = 模拟竖式，从个位（末尾）逐位加。双指针 i、j 从两串末尾往前走，每位 sum = d1 + d2 + carry，写 sum % 10、进位 carry = sum / 10，短串高位补 0。三个关键：循环条件必须含 carry != 0（否则漏最高位进位，如 99+1）、字符减 ‘0’ 转数值、最后 reverse 反转。这套模板通吃链表两数相加、字符串相乘、二进制求和。核心：竖式逐位加、进位别漏、结果记得翻。

简化版

详细版