大家好，我是 @负雪明烛。欢迎关注。

前言

加法是我们上小学的时候开始学习的第一种数学运算。
在算法题中，「求加法」问题大多考察「列竖式」求和。
题目中，「两数之和」通常与其他形式表示的数字结合起来：

  • 两个字符串形式的数字相加（第 415 题）
  • 两个链表形式的数字相加（第 2 、445、369 题）
  • 数组形式的数字相加（第 66 、989题）
  • 两个二进制形式的数字相加（第 67 题）

做法都是非常类似的，本质是在考察各种数据表示形式：字符串，链表，数组，二进制。
我们只要掌握了用「列竖式」求「两数之和」的方法，这类题目全都可以秒杀。

十进制加法

我们先回顾一下十进制加法的计算过程：
989. 数组形式的整数加法 - 图1
使用「竖式」计算十进制的加法的方式：

  1. 两个「加数」的右端对齐；
  2. 从最右侧开始，从右向左依次计算对应的两位数字的和，如果有进位需要加上进位。如果和大于等于 10，则把和的个位数字计入结果，并向前面进位；
  3. 重复步骤 2；

  4. 当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中。

    在实现中需要注意的有：

  5. 不可以把字符串表示的「加数」先转化成 int 型数字再求和，因为可能溢出；

  6. 两个「加数」的字符串长度可能不同；
  7. 在最后，如果进位 carry 不为 0，那么最后需要计算进位。
  8. 注意 结果数字 是否为低位结果在前，根据题目要求判断最后是否要反转结果。

    解题方法

    题目要我们求一个数组形式表示的数字和一个 int 形式表示的数字相加，按照「列竖式」的方法进行求解即可。

代码说明

  1. while (p1 >= 0 || k != 0 || carry > 0)含义：
    1. 字符串 num 和数字 k 只要有一个没遍历完，那么就继续遍历；
    2. 如果字符串 num 和数字 k 都遍历完了，但是最后留下的进位 carry != 0，那么需要把进位也保留到结果中。
  2. 取 adder 的时候，如果字符串 num 和 数字 k 中有一个已经遍历完了（即 989. 数组形式的整数加法 - 图2 或者 989. 数组形式的整数加法 - 图3），则认为 num 和 k 的对应位置是 989. 数组形式的整数加法 - 图4 。

代码

该代码可以作为「求加法」的模板。

Java / C++ / Python 三种语言代码如下：

  1. class Solution {
  2.     public List<Integer> addToArrayForm(int[] num, int k) {
  3.         List<Integer> res = new ArrayList<>(); // 返回结果
  4.         int p1 = num.length - 1; // 标记遍历到 num 的位置
  5.         int carry = 0; // 进位
  6.         while (p1 >= 0 || k != 0 || carry != 0) { // num 没遍历完，或 k 没遍历完，或进位不为 0
  7.             int adder1 = p1 >= 0 ? num[p1] : 0; // 当前 num 的取值
  8.             int adder2 = k % 10; // 当前 k 的位置，如果 k 已经是 0 那么 % 10 以后仍然是 0
  9.             int sum = adder1 + adder2 + carry; // 当前位置相加的结果
  10.             carry = sum >= 10 ? 1 : 0; // 是否有进位
  11.             sum = sum >= 10 ? sum - 10 : sum; // 去除进位后留下的数字
  12.             res.add(sum); // 把去除进位后留下的数字拼接到结果中
  13.             p1 --; // 遍历到 num 的位置向左移动
  14.             k /= 10; // 取 k 的下一个位置的数字
  15.         }
  16.         Collections.reverse(res); // 把结果反转
  17.         return res; 
  18.     }
  19. }
  1. class Solution {
  2. public:
  3.     string addStrings(string num1, string num2) {
  4.         const int M = num1.size();
  5.         const int N = num2.size();
  6.         string res;
  7.         int p1 = M - 1;
  8.         int p2 = N - 1;
  9.         int carry = 0;
  10.         while (p1 >= 0 || p2 >= 0 || carry > 0) {
  11.             int cur1 = p1 >= 0 ? num1[p1] - '0' : 0;
  12.             int cur2 = p2 >= 0 ? num2[p2] - '0' : 0;
  13.             int sum = cur1 + cur2 + carry;
  14.             carry = sum >= 10 ? 1 : 0;
  15.             sum = sum >= 10 ? sum - 10 : sum;
  16.             res += to_string(sum);
  17.             p1 --;
  18.             p2 --;
  19.         }
  20.         reverse(res.begin(), res.end());
  21.         return res;
  22.     }
  23. };
  1. class Solution(object):
  2.     def addToArrayForm(self, num, k):
  3.         p1 = len(num) - 1
  4.         carry = 0
  5.         res = []
  6.         while p1 >= 0 or k != 0 or carry > 0:
  7.             adder1 = num[p1] if p1 >= 0 else 0
  8.             adder2 = k % 10
  9.             sum = adder1 + adder2 + carry
  10.             carry = 1 if sum >= 10 else 0
  11.             sum = sum - 10 if sum >= 10 else sum
  12.             res.append(sum)
  13.             p1 -= 1
  14.             k //= 10
  15.         return res[::-1]

复杂度分析

  1. 「求加法」系列题目都不难，其实就是 「列竖式」计算。
  2. 需要注意的是：
    1. while循环结束条件；
    2. 遍历两个「加数」不要越界；
    3. 进位；
    4. 最后的结果需要翻转。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。