题目描述

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：

输入： num1 = "11", num2 = "123"
输出： "134"

示例 2：

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

示例 3：

输入： num1 = "0", num2 = "0"
输出： "0"

提示：

• 1 <= num1.length, num2.length <= 104
• num1 和num2 都只包含数字 0-9
• num1 和num2 都不包含任何前导零

分析解答

这道题本质是实现「大整数加法」，也就是模拟我们手写的“竖式加法”，要求不能用内建的 BigInt 或强转数字。

---

✅ 解题思路（模拟加法，倒着算）

我们从两个字符串的尾部开始加，每次加一位，同时维护一个 进位 carry，然后构造结果字符串。

---

✅ TypeScript 实现

双指针。

function addStrings(num1: string, num2: string): string {let i = num1.length - 1;let j = num2.length - 1;let carry = 0;let res = '';while (i >= 0 || j >= 0 || carry > 0) {const n1 = i >= 0 ? parseInt(num1[i]) : 0;const n2 = j >= 0 ? parseInt(num2[j]) : 0;const sum = n1 + n2 + carry;res = (sum % 10) + res;carry = Math.floor(sum / 10);i--;j--;}return res;
}

---

🔍 示例解析

示例 1：num1 = "456", num2 = "77"

   4 5 6
+     7 7
---------5 3 3 ✅

过程：

• 6 + 7 = 13 → 写 3，进位 1
• 5 + 7 + 1 = 13 → 写 3，进位 1
• 4 + 0 + 1 = 5 → 写 5，进位 0

结果："533"

---

✅ 时间和空间复杂度

• 时间复杂度：O(max(m, n))，m 和 n 是两个字符串的长度
• 空间复杂度：O(max(m, n))，结果字符串长度

---

思路拓展

这道题最好的做法就是双指针，直接操作字符串，如果使用数组的话，很容易出现超时或者栈溢出的报错。

写法一 - 超时做法

🚨 unshift() 是在数组最前面插入一个元素，它的时间复杂度是：

O(n) —— 每次都需要移动数组中已有的所有元素！

function addStrings(num1: string, num2: string): string {const arr1 = num1.split('')const arr2 = num2.split('')const res: number[] = []let carry = 0while (arr1.length || arr2.length || carry) {let num1 = arr1.length ? Number(arr1.pop()) : 0let num2 = arr2.length ? Number(arr2.pop()) : 0let sum = num1 + num2 + carryif (sum >= 10) carry = 1let cur = sum % 10res.unshift(cur)}return String(res.join())
};

写法二 - ?? 的错误使用

function addStrings(num1: string, num2: string): string {const arr1 = num1.split('')const arr2 = num2.split('')const res: number[] = []let carry = 0while (arr1.length || arr2.length || carry) {let num1 = Number(arr1.pop()) ?? 0let num2 = Number(arr2.pop()) ?? 0let sum = num1 + num2 + carryif (sum >= 10) carry = 1let cur = sum % 10res.push(cur)}return res.reverse().join('')
};

arr1.pop() 返回的是 string | undefined

如果是 undefined，传给 Number(…) 就变成 NaN

所以 Number(undefined) ?? 0 实际上返回的是 NaN，不会走到 ?? 0，因为 NaN ≠ null 或 undefined

正确的写法可以改为：

const n1 = arr1.length ? Number(arr1.pop()) : 0;
const n2 = arr2.length ? Number(arr2.pop()) : 0;// 或者是
const n1 = Number(arr1.pop() ?? '0');
const n2 = Number(arr2.pop() ?? '0');

写法三 - 栈溢出

function addStrings(num1: string, num2: string): string {const arr1 = num1.split('')const arr2 = num2.split('')const res: number[] = []let carry = 0while (arr1.length || arr2.length || carry) {let num1 = arr1.length ? Number(arr1.pop()) : 0let num2 = arr2.length ? Number(arr2.pop()) : 0let sum = num1 + num2 + carryif (sum >= 10) carry = 1let cur = sum % 10res.push(cur)}return res.reverse().join('')
}; 

报错：<— Last few GCs —>
[20:0xcfe3000] 1289 ms: Mark-Compact (reduce) 386.9 (396.3) -> 386.8 (389.3) MB, pooled: 0 MB, 46.23 / 0.00 ms (average mu = 0.639, current mu = 0.003) last resort; GC in old space requested
[20:0xcfe3000] 1340 ms: Mark-Compact (reduce) 386.8 (389.3) -> 386.8 (389.1) MB, pooled: 0 MB, 50.45 / 0.00 ms (average mu = 0.501, current mu = 0.000) last resort; GC in old space requested
<— JS stacktrace —>
FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
----- Native stack trace -----
1: 0xe36196 node::OOMErrorHandler(char const*, v8::OOMDetails const&) [nodejs run]

主要报错就是：JavaScript heap out of memory 内存溢出

这并不是代码逻辑有错，而是程序运行时占用了太多内存，触发了 V8 的内存限制（默认约为 512MB - 1.5GB）。因为是大数相加，所以同时频繁的：

pop()

Number(…)

res.push(…)

res.reverse()

join(‘’)

都会在大输入下产生巨大的临时对象 → 导致 GC频繁触发，最终内存耗尽。

虽然以下做法可以正常通过，但是并不推荐：

function addStrings(num1: string, num2: string): string {const arr1 = num1.split('');const arr2 = num2.split('');const res: number[] = [];let carry = 0;while (arr1.length || arr2.length || carry) {const n1 = arr1.length ? Number(arr1.pop()) : 0;const n2 = arr2.length ? Number(arr2.pop()) : 0;const sum = n1 + n2 + carry;res.push(sum % 10);carry = Math.floor(sum / 10);}return res.reverse().join('');
}