415. 字符串相加

LeetCode 原题链接

题目描述

给定两个非负整数字符串 num1 和 num2，返回它们的和。不能直接使用大整数库，也不能把整个字符串转换成整数。

输入：num1 = "456", num2 = "77"
输出："533"

题型判断

这是竖式加法模拟题。个位在字符串末尾，所以用两个指针从右向左逐位相加，并维护进位 carry。

核心过程

  456
+  77
-----
当前位计算写入新进位
个位6 + 7 + 0 = 1331
十位5 + 7 + 1 = 1331
百位4 + 0 + 1 = 550

代码实现

var addStrings = function (num1, num2) {
  let n1 = num1.length - 1;
  let n2 = num2.length - 1;

  let carry = 0;
  let answer = "";

  while (n1 >= 0 || n2 >= 0 || carry > 0) {
    const v1 = n1 >= 0 ? Number(num1[n1]) : 0;
    const v2 = n2 >= 0 ? Number(num2[n2]) : 0;
    const sum = v1 + v2 + carry;

    const currentDigit = sum % 10;
    carry = Math.floor(sum / 10);

    answer = currentDigit + answer;

    n1--;
    n2--;
  }

  return answer;
};

复杂度与易错点

  • 时间复杂度：O(max(m, n))。
  • 空间复杂度：O(max(m, n))，用于保存结果。
  • 循环条件必须包含 carry > 0，否则 "9" + "1" 会漏掉最高位。
  • 两个字符串长度不同时，越界一侧按 0 处理。

常见错误分析

1. 直接用索引作为循环条件

不能写成：

while (n1 || n2 || carry) {
  // ...
}

索引为 0 时仍有一位需要处理，但 0 是假值；索引为 -1 时已经越界，但 -1 反而是真值。必须显式判断：

while (n1 >= 0 || n2 >= 0 || carry > 0) {
  // ...
}

2. 忘记把字符转换成数字

通过下标取得的 num1[n1] 和 num2[n2] 都是字符串。直接使用 + 会触发字符串拼接：

"1" + "2" + 0; // "120"

因此相加前需要使用 Number() 转换成数字。

3. 索引没有递减到 -1

不能只在索引大于 0 时递减：

if (n1 > 0) n1--;

这样指针到达 0 后会一直停留在原地。每轮处理完成后直接执行 n1-- 和 n2-- 即可。

另外，进位变量应该命名为 carry。curry 通常用于表示函数柯里化，虽然不会造成运行错误，但容易引起误解。