LeetCode 989. 数组形式的整数加法

约 9 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节跳动 华为
标签
数组 数学 加法问题
目录

题目描述

✅ 989. 数组形式的整数加法

image-20230312173924486

题意分析

给的不是一个整数，而是一个把整数按十进制逐位拆开的数组 num，num[0] 是最高位、num[n-1] 是个位。要求把它和一个普通整数 k 相加，结果仍然以「逐位数组」的形式返回。

第一个必须先想清楚的问题是：能不能把 num 还原成一个整数再加？不能。num.length 最大是 $10^4$，这意味着这个数最大有一万位，远远超出 64 位整数的表示范围，任何「先拼成 long 再相加」的写法都会在长数组上直接溢出。数组长度这个约束就是在告诉你：答案必须逐位产生，全程不能出现一个代表整体数值的变量。

第二个信号来自数据形态本身。十进制加法天然是从低位往高位做的，而低位在数组的末尾，所以遍历方向必然是从右向左；同时结果也是先算出低位，所以收集结果的顺序与最终要返回的顺序恰好相反，最后需要翻转。

边界主要有三处。一是两个加数长度不等，k 最大 $10^4$ 只有 5 位，而 num 可能有一万位，短的一方先耗尽，之后还要继续把长的一方抄下来。二是最高位可能产生新的进位，比如 [9,9] + 1，结果 [1,0,0] 比原数组还长一位。三是反过来，num = [0]、k = 0 这类极小输入必须返回 [0] 而不是空数组。

解法：从后向前模拟

核心思路

最直白的想法是把 num 拼成整数、加上 k、再拆回数组。它的瓶颈非常硬：一万位的数根本装不进任何原生整数类型，这条路在题目给出的规模下直接不成立。退一步用大整数类库，等于把考点（进位模拟）整个绕过去了，面试里不会被接受。

于是只能回到小学竖式：每一位的结果只取决于「本位两个加数之和 + 上一位的进位」，与更高位无关。这条局部性正是竖式加法可以逐位推进的根本原因，也让我们完全不需要知道整体数值。

把 k 也看成一个可以逐位取出的加数就统一了两边的处理方式：k % 10 是它当前的个位，k /= 10 相当于把 k 的指针左移一位。这样 num 用下标 i 从右往左走，k 用整除不断缩短，两者变成完全对称的两条流。

循环维持的不变量是：每一轮开始时，carry 是比当前位低一位的所有位相加后向当前位产生的进位，而 res 里已经按从低位到高位的顺序存好了所有已经定型的结果位。每轮取出两条流的当前位与 carry 求和，sum % 10 是新定型的一位，sum / 10 成为下一轮的 carry，不变量得以维持。

循环的终止条件是三者同时枯竭：i < 0 且 k == 0 且 carry == 0。把 carry > 0 也写进循环条件，是让「最高位再进一位」这种情况自然多跑一轮，而不需要在循环外补一个特判分支。

解题步骤

  • 准备结果容器与两条流的游标：res 用来按低位到高位追加结果，i = num.length - 1 指向 num 的个位，carry = 0 表示个位之前没有进位。之所以从末尾开始，是因为加法的信息只能从低位向高位单向流动。
  • 循环条件写成 i >= 0 || k > 0 || carry > 0：三个条件是「或」不是「与」。用「或」才能覆盖两个加数长度不等的情况——短的一方耗尽后，长的一方仍要继续被抄写；carry > 0 这一项则专门负责最高位溢出时多产生的那一位。
  • 每轮先把 carry 装进 sum：sum 的语义是「本位的总和」，进位是上一轮遗留给本位的一部分，所以它必须是第一个被累加进来的。
  • 有条件地取两个加数的当前位：i >= 0 时累加 num[i--]，k > 0 时累加 k % 10 并执行 k /= 10。这两个判断不能省——越界取值会抛异常，而对已经归零的 k 继续取模只是徒劳。
  • 拆分 sum 得到本位与新进位：res.add(sum % 10) 落定当前位，carry = sum / 10 传给下一轮。因为每轮最多两个个位数字加一个进位，sum 不会超过 19，所以 carry 只会是 0 或 1。
  • 最后翻转 res：结果是从个位开始追加的，与题目要求的「最高位在前」正好相反，必须翻转一次再返回。

以 num = [2,7,4]、k = 181 走一遍。

初始：i = 2、k = 181、carry = 0、res = []。

第一轮：sum = 0 + num[2] + 181 % 10 = 0 + 4 + 1 = 5，k 变成 18，i 变成 1；res = [5]，carry = 0。

第二轮：sum = 0 + num[1] + 18 % 10 = 0 + 7 + 8 = 15，k 变成 1，i 变成 0；res = [5,5]，carry = 1。

第三轮：sum = 1 + num[0] + 1 % 10 = 1 + 2 + 1 = 4，k 变成 0，i 变成 -1；res = [5,5,4]，carry = 0。

此时三个条件全部不成立，循环退出。翻转 res 得到 [4,5,5]，即 274 + 181 = 455，正确。

再看一个产生额外高位的用例 num = [9,9]、k = 1：第一轮 sum = 0 + 9 + 1 = 10，落位 0、carry = 1；第二轮 sum = 1 + 9 = 10，落位 0、carry = 1；此时 i < 0 且 k == 0，但 carry > 0 让循环再跑一轮，sum = 1，落位 1。翻转后得到 [1,0,0]，长度比原数组多了一位。

代码实现

class Solution {
    // 每次取余作为当前位，进位继续。
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> res = new ArrayList<>();
        int i = num.length - 1;
        int carry = 0;

        while (i >= 0 || k > 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) {
                sum += num[i--];
            }
            if (k > 0) {
                sum += k % 10;
                k /= 10;
            }

            res.add(sum % 10);
            carry = sum / 10;
        }

        Collections.reverse(res);
        return res;
    }
}

func addToArrayForm(num []int, k int) []int {
    // 每次取余作为当前位，进位继续。
    res := make([]int, 0)
    i := len(num) - 1
    carry := 0

    for i >= 0 || k > 0 || carry > 0 {
        sum := carry
        if i >= 0 {
            sum += num[i]
            i--
        }
        if k > 0 {
            sum += k % 10
            k /= 10
        }

        res = append(res, sum%10)
        carry = sum / 10
    }

    for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
        res[l], res[r] = res[r], res[l]
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n + \log k)$，其中 $n$ 是数组长度。循环轮数由两条流中较长的一条决定：num 贡献 $n$ 轮，k 每轮除以 10 只能贡献 $\log_{10} k$ 轮，最高位进位最多再多一轮，每轮内部都是常数次算术运算。
  • 空间复杂度：$O(1)$，不计返回的结果数组，只用了 i、carry、sum 三个标量；结果数组长度最多是 $\max(n, \log k) + 1$，属于必须的输出开销。

关键点总结

  • 看到「用数组表示一个超长整数」，第一反应就该是禁止还原成原生整数，逐位模拟是唯一可行的方向，这条判断在字符串相加、大数相乘等题里完全通用。
  • 竖式加法的局部性——本位结果只依赖本位两个加数与低位进位——是所有进位模拟题的共同内核，写代码前先把这句话说出来，思路就不会乱。
  • 把「长度不等」「最高位溢出」都塞进循环条件（i >= 0 || k > 0 || carry > 0），比在循环外补特判更短也更不容易漏；面试时主动指出这个设计，是体现代码品味的地方。
  • 用 k % 10 与 k /= 10 把整数也当成一条可逐位取出的流，能让两个形态不同的加数用同一套逻辑处理，这是「统一表示后再统一处理」的典型应用。
  • 从低位生成、最后翻转，是进位模拟的标准收尾；如果用的是支持头插的结构（如链表或 LinkedList），也可以直接头插省掉翻转，面试时值得提一句作为权衡。

易错点总结

  • 把 num 拼成 int 或 long 再相加：num 长度可达 $10^4$，例如一个由一万个 9 组成的数组，拼接过程早就溢出，结果是一个毫无意义的负数或截断值。
  • 循环条件写成 i >= 0 && k > 0：num = [1,2,3]、k = 4 时，k 在第一轮就归零，循环立刻结束，只算出个位，返回 [7] 而丢掉了高位的 12。
  • 忘记 carry > 0 这一项：num = [9,9]、k = 1 时循环在两轮后结束，最高位那个进位无处落地，返回 [0,0] 而不是 [1,0,0]。
  • 忘记最后翻转结果：num = [1,2]、k = 34 会返回 [6,4]，恰好是正确答案 [4,6] 的逆序，而在 [1,2]、k = 21 这种回文结果上又碰巧「对」了，导致这个 bug 很容易被弱用例放过。
  • sum 忘记加 carry：num = [9]、k = 9 时第一轮落位 8、carry = 1，第二轮 sum 从 0 起算得到 0，返回 [0,8] 而不是 [1,8]。
  • 取 k 的当前位时写成 k % 10 却漏掉 k /= 10：k = 12 会每轮都取到 2，且 k > 0 永远成立，循环变成死循环。
  • 用 carry = sum % 10、本位取 sum / 10：两者写反，sum = 15 时会把 1 当作本位、5 当作进位，[9] + 6 返回 [5,1] 这种彻底错乱的结果。
  • 访问 num[i] 前不判断 i >= 0：num = [1]、k = 999 时第二轮就会以 i = -1 取值，抛出数组越界异常。
  • 对结果做「去前导零」处理：num = [0]、k = 0 时若把前导零全部剥掉会返回空数组，而正确答案是 [0]。

相似题目

题目 难度 考察点
66. 加一 简单 加数固定为 1，只在连续 9 的后缀上才需要进位，可提前跳出
415. 字符串相加 简单 两个加数都是超长字符串，需双指针同时从尾部回退并做字符与数字转换
67. 二进制求和 简单 把基数从 10 换成 2，取余与整除的除数随之改变
2. 两数相加 中等 加数存在逆序链表里，天然从低位开始，用哨兵节点边算边接
445. 两数相加 II 中等 链表是正序存储，需要用栈或反转链表把低位先取出来
43. 字符串相乘 中等 乘法要用下标关系定位乘积落在哪两位，进位处理比加法多一层
1073. 负二进制数相加 中等 基数为 -2，进位可能是 -1，需要额外的借位规则
LCR 002. 二进制求和 简单 与 67 同题
面试题 02.05. 链表求和 中等 与 2 同题
补充题 9. 36进制加法 中等 基数换成 36，需要在字符与数值之间做双向映射