题目描述
给定两个字符串形式的非负整数 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 <= 104num1和num2都只包含数字0-9num1和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 = 0
while (arr1.length || arr2.length || carry) {
let num1 = arr1.length ? Number(arr1.pop()) : 0
let num2 = arr2.length ? Number(arr2.pop()) : 0
let sum = num1 + num2 + carry
if (sum >= 10) carry = 1
let cur = sum % 10
res.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 = 0
while (arr1.length || arr2.length || carry) {
let num1 = Number(arr1.pop()) ?? 0
let num2 = Number(arr2.pop()) ?? 0
let sum = num1 + num2 + carry
if (sum >= 10) carry = 1
let cur = sum % 10
res.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 = 0
while (arr1.length || arr2.length || carry) {
let num1 = arr1.length ? Number(arr1.pop()) : 0
let num2 = arr2.length ? Number(arr2.pop()) : 0
let sum = num1 + num2 + carry
if (sum >= 10) carry = 1
let cur = sum % 10
res.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('');
}