LeetCode 415. 字符串相加

约 5 分钟
文章信息 23 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 200-500 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 小米 百度 快手 滴滴 携程 B站 虾皮 BOSS直聘 猿辅导
标签
字符串 数学 模拟

题目描述

✅ 415. 字符串相加

image-20260928184257678

题意分析

num1 和 num2 分别用十进制字符串表示一个非负整数，要求返回它们相加后的字符串。数字可能很长，不能先把整个字符串转换成整数，也不能借助大整数库直接求和，但可以读取并计算单个数字。

两个字符串长度可能不同，运算还可能在最高位产生额外进位。要得到完整结果，既要保留较长一侧尚未处理的数字，也要处理两个字符串都读完后的进位。

解法：双指针模拟竖式加法

核心思路

[!blue]

加法中，高位需要接收低位产生的进位，因此应从最低位向最高位计算。字符串末尾是个位，让 i、j 分别从两个字符串末尾向前移动，就能把同一位上的数字对齐。

carry 保存上一轮低位传来的进位。每轮把两个当前数字与 carry 相加得到 sum，当前结果位是 sum % 10，传给下一位的进位是 sum / 10 的整数部分。单个数字最多为 9，所以 sum 最多为 19，无需用大整数计算局部结果。

如果某个指针已经越过开头，这一侧在更高位没有数字，按 0 参与计算即可。只要任一字符串还有数字，或 carry 仍不为 0，就还存在需要处理的一位；这三种情况必须用“或”连接。

每轮确定的低位不会再被后续高位改变，所以可以立即写入结果缓冲区。由于写入顺序是从低位到高位，最后统一反转即可恢复正常顺序；尾部追加也避免了反复向字符串头部插入带来的搬移。

解题步骤

  1. 初始化 i = num1.length - 1、j = num2.length - 1，进位 carry = 0，并创建结果缓冲区。
  2. 当 i >= 0、j >= 0、carry > 0 至少一个成立时，开始计算下一位。
  3. 先令 sum = carry。分别检查两个指针是否有效，有效时减去字符 '0' 得到数字，累加到 sum，再前移该指针。
  4. 把 sum % 10 写入结果，将 carry 更新为 sum / 10。
  5. 循环结束后反转缓冲区并返回。Java 的 append(int) 直接写入该数字，Go 则先加上 '0' 转成对应字符。

代码实现

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder builder = new StringBuilder();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;

        // 较长数的剩余高位和最后进位都需要继续处理。
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;

            if (i >= 0) {
                sum += num1.charAt(i) - '0';
                i--;
            }

            if (j >= 0) {
                sum += num2.charAt(j) - '0';
                j--;
            }

            // 当前个位写入逆序缓冲，高位进位留给下一轮。
            builder.append(sum % 10);
            carry = sum / 10;
        }

        return builder.reverse().toString();
    }
}

func addStrings(num1 string, num2 string) string {
    res := make([]byte, 0)
    i := len(num1) - 1
    j := len(num2) - 1
    carry := 0

    // 较长数的剩余高位和最后进位都需要继续处理。
    for i >= 0 || j >= 0 || carry > 0 {
        sum := carry
        if i >= 0 {
            sum += int(num1[i] - '0')
            i--
        }
        if j >= 0 {
            sum += int(num2[j] - '0')
            j--
        }

        // 当前个位写入逆序缓冲，高位进位留给下一轮。
        res = append(res, byte(sum%10)+'0')
        carry = sum / 10
    }

    for left, right := 0, len(res)-1; left < right; left, right = left+1, right-1 {
        res[left], res[right] = res[right], res[left]
    }
    return string(res)
}

复杂度分析

设两个字符串长度分别为 m、n。

  • 时间复杂度：$O(\max(m,n))$，最多计算较长字符串的位数再加一位，反转同样需要线性时间。
  • 空间复杂度：$O(\max(m,n))$，用于保存结果缓冲区；除结果相关存储外只使用常数个变量。

关键点总结

[!green]

  • 从右向左读取才能先确定低位，再把进位交给高位。
  • 已读完的一侧按 0 处理，让不同长度的输入共用同一套逻辑。
  • 输入读完和运算结束不是同一件事，最后的进位也可能单独形成一位。

易错点总结

[!yellow]

  • 循环只检查两个指针，会漏掉最高位进位；只要 carry > 0 就应继续。
  • 使用 && 连接条件，会在较短字符串耗尽时提前停止，丢失较长字符串的高位。
  • 直接累加字符编码而不减 '0'，得到的不是数字和；Go 写回字符时还需要加 '0'。
  • 忘记反转缓冲区，会把结果按低位在前的顺序返回。

相似题目

题目 难度 关联与区别
2. 两数相加 中等 同样逐位求和与进位，链表低位在前，本题从字符串末尾读取低位。
43. 字符串相乘 中等 字符串乘法会产生多组部分积，仍需复用位权对齐与进位累加。
445. 两数相加 II 中等 逐位计算并维护进位；本题按十进制字符相加，该题高位在前需反转或栈辅助。
66. 加一 简单 逐位计算并维护进位；本题按十进制字符相加，该题加一时只传播单次进位。
67. 二进制求和 简单 逐位计算并维护进位；本题按十进制字符相加，该题按二进制位相加。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/09159489
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！