題目描述

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('');
}