算法 - 字符串相加（大数相加）

Posted on

1. 题目

给定两个用字符串表示的非负整数 num1 和 num2，计算它们之和，并用字符串形式返回。

要求：不能直接使用任何内置的大整数库，也不能把整个输入字符串直接转换成整数（会溢出）。

示例:

1
2
3
4
5
输入: num1 = "11", num2 = "123"
输出: "134"

输入: num1 = "999", num2 = "1"
输出: "1000"

2. 解题思路

模拟小学竖式加法，从**个位（字符串末尾）**开始逐位相加并处理进位。

2.1 双指针从尾部向前

  • i、j 分别指向 num1、num2 的末尾，carry 为进位。

  • 每一步：取当前位数字（指针越界则视为 0），sum = d1 + d2 + carry。

  • 当前结果位 = sum % 10，新的 carry = Math.floor(sum / 10)。

  • 结果字符往前拼接（或 push 后反转）。

  • 循环条件：i >= 0 || j >= 0 || carry——最后的 carry 不能漏。

  • 时间复杂度：O(max(m, n))，空间复杂度：O(max(m, n))（结果串）。

3. TypeScript 实现

3.1 标准双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function addStrings(num1: string, num2: string): string {
    let i = num1.length - 1;
    let j = num2.length - 1;
    let carry = 0;
    const res: string[] = [];

    while (i >= 0 || j >= 0 || carry > 0) {
        const d1 = i >= 0 ? num1.charCodeAt(i) - 48 : 0; // '0'.charCodeAt = 48
        const d2 = j >= 0 ? num2.charCodeAt(j) - 48 : 0;
        const sum = d1 + d2 + carry;

        res.push(String(sum % 10));
        carry = Math.floor(sum / 10);

        i--;
        j--;
    }

    return res.reverse().join("");
}

console.log(addStrings("999", "1")); // "1000"

3.2 变体：字符串相乘（大数乘法）

同族题，用 i + j、i + j + 1 定位乘积位在结果数组中的落点，双循环累加后再统一处理进位。面试常作为追问。

4. 面试延伸

  • 为何用 charCodeAt 而非 parseInt：逐字符 + '0' 或 charCodeAt - 48 更快，且体现「不整体转 int」的约束。
  • JS 的坑：Number 只有 53 位安全整数（Number.MAX_SAFE_INTEGER），超大数相加若直接 + 会丢精度——这正是本题要求模拟竖式的现实动机；实际项目大数运算常用 BigInt。
  • 相关：链表版本「两数相加」(LeetCode 2)，用链表节点从低位到高位模拟同样的进位逻辑。
  • 结果拼接用数组 push + 反转，避免字符串反复 += 头部的 O(n²) 开销。

难度：简单 | LeetCode 415 | 字符串/模拟