解决方案

方法一：逐位相加

思路

让我们逐位将数字加在一起。举一个例子，如果要计算 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))$$ ，其中 $$N$$ 是数组 A 的长度。

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