题目

标题和出处

标题：数组形式的整数加法

出处：989. 数组形式的整数加法

难度

3 级

题目描述

要求

整数 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 ，那么其数组形式为 。

给定一个整数的数组形式 和一个整数 ，返回整数 的数组形式。

示例

示例 1：

输入：
输出：
解释：

示例 2：

输入：
输出：
解释：

示例 3：

输入：
输出：
解释：

示例 4：

输入：
输出：
解释：

数据范围

• 
• 
• 除了整数 之外， 不会以零开头
• 

解法

思路和算法

这道题是「加一」的一般化情况，把「加 」换成了「加 」。这道题同样可以通过模拟加法过程的方法得到结果。

首先将数组 的右边第一位加 ，如果在更新之后，第一位大于 ，则产生进位，将进位加到第二位，第一位保留个位。如果在进位操作之后，第二位大于 ，则继续处理进位。在该过程中，使用动态数组存储数组 的从低到高的每一位，除了最高位。

数组 的最高位可能大于 ，因此需要将最高位的每一个数位按照从低到高的顺序添加到动态数组中。需要注意的是，由于数组 表示的数字和 都可能是 ，因此当数组 的最高位是 时，也需要被添加到动态数组中。

对数组 的最高位处理结束后，此时动态数组中的元素是结果的每一位，每个元素都是一位数，元素按照从最低位到最高位的顺序排列。将动态数组中的元素进行反转，即可得到最终结果。

代码

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> sum = new ArrayList<Integer>();
        int length = num.length;
        num[length - 1] += k;
        for (int i = length - 1; i > 0; i--) {
            int curNum = num[i];
            if (curNum > 9) {
                num[i - 1] += curNum / 10;
                num[i] %= 10;
            }
            sum.add(num[i]);
        }
        do {
            sum.add(num[0] % 10);
            num[0] /= 10;
        } while (num[0] > 0);
        Collections.reverse(sum);
        return sum;
    }
}

复杂度分析

• 时间复杂度：)#card=math&code=O%28%5Cmax%28n%2C%5Clog_%7B10%7D%20k%29%29&id=sfUwI)，其中 是数组 的长度。需要遍历数组 和数字 的每一位，完成加法的计算。
• 空间复杂度：#card=math&code=O%281%29&id=xv6wS)。除了返回值以外，使用的空间复杂度是常数。