LeetCode 989. 数组形式的整数加法
题目描述
题意分析
数组
num从高位到低位保存一个整数的十进制数字，要求返回它与k相加后的数字数组。数组最多有一万位，不能先把它整体转换成固定宽度整数，但每一位的加法仍然可以直接计算。
解法：从后向前模拟
核心思路
[!blue]
按竖式加法从个位开始处理。用
i指向num尚未处理的最低位；k % 10取得另一个加数的当前最低位，k /= 10去掉这一位；carry保存上一轮从低位传来的进位。每轮令
sum等于两边当前数字与carry之和。某一边已经没有数字时，就把它在这一位上的贡献视为 $0$。当前结果位是sum % 10，传给下一位的进位是sum / 10。两边数字最多各为 $9$，进位最多为 $1$，所以每轮局部计算都很小，不受整个整数长度影响。处理完一轮后，结果中已经确定的低位无需再改变，
i、剩余k和carry则描述所有尚未处理的高位。因此循环必须在“数组还有数字、k还有数字、还有进位”任一条件成立时继续。即使两个加数都耗尽，最后的进位也可能单独形成一位。数字按从低位到高位的顺序产生，先追加到列表尾部，最后统一反转即可得到题目要求的高位在前顺序。无需不断向列表头部插入，也不会改变原数组。
解题步骤
- 初始化
i = num.length - 1、carry = 0和结果列表。- 当
i >= 0 || k > 0 || carry > 0时，以carry为本轮和的初值，再加入两边仍存在的当前数字。- 将
sum % 10追加到结果，令carry = sum / 10，已使用的数组位置和k的个位都不再保留。- 循环结束后反转结果并返回。
代码实现
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(\max(n,d))$，其中
n是数组长度，d是k的十进制位数；每轮处理一位，最终最多再处理一次进位，反转也是线性时间。- 空间复杂度：除返回结果外为 $O(1)$；结果最多有 $\max(n,d)+1$ 位。
关键点总结
[!green]
- 循环条件是多个来源的或，不是要求两边都有剩余位。
- 最后进位可能使结果增加一位。
易错点总结
[!yellow]
- 只循环数组长度，会漏掉 k 更高位或最终进位。
- 先把 sum 覆盖为除十的商，再从 sum 取个位，会丢失本轮原始和的个位。
- 结果不反转，会把低位顺序直接返回。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 66. 加一 | 简单 | 把固定加1推广为加整数k，仍从数组低位开始处理进位。 |
| 415. 字符串相加 | 简单 | 同样模拟十进制加法，本题一个加数是数字数组，另一个可边取余边消耗。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！