989. 数组形式的整数加法

989. 数组形式的整数加法

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

示例 1：

输入：A = [1,2,0,0], K = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234
解释 2：

输入：A = [2,7,4], K = 181
输出：[4,5,5]
解释：274 + 181 = 455
示例 3：

输入：A = [2,1,5], K = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021
示例 4：

输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
输出：[1,0,0,0,0,0,0,0,0,0,0]
解释：9999999999 + 1 = 10000000000

提示：

1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
如果 A.length > 1，那么 A[0] != 0
解决方案：逐位相加

class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        int N = A.length;
        int cur = K;
        List<Integer> ans = new ArrayList();

        int i = N;
        while (--i >= 0 || cur > 0) {
            if (i >= 0)
                cur += A[i];
            ans.add(cur % 10);
            cur /= 10;
        }

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

思路

让我们逐位将数字加在一起。举一个例子，如果要计算 123 与 912 的和。我们顺次计算 3+2、2+1、1+9。任何时候，当加法的结果大于等于 10 ，我们要将进位的 1 加入下一位的计算中去，所以最终结果等于 1035。

算法

我们可以对以上的想法做一个小变化，让它实现起来更容易 —— 我们将整个加数加入数组表示的数的最低位。

继续之前的例子 123+912，我们把它表示成 [1, 2, 3+912]。然后，我们计算 3+912 = 915。5 留在当前这一位，将 910/10=91 以进位的形式加入下一位。

然后，我们再重复这个过程，计算 [1, 2+91, 5]。我们得到 93，3 留在当前位，将 90/10=9 以进位的形式加入下一位。继而又得到 [1+9, 3, 5]，重复这个过程之后，最终得到结果 [1, 0, 3, 5]。

复杂度分析

时间复杂度： O(\max(N, \log K))O(max(N,logK))，其中 NN 是数组 A 的长度。

空间复杂度： O(\max(N, \log K))O(max(N,logK))。