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

前言

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

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

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

十进制加法

我们先回顾一下十进制加法的计算过程：
415. 字符串相加 - 图1
使用「竖式」计算十进制的加法的方式：

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

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

    在实现中需要注意的有：

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

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

    解题方法

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

代码说明

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

代码

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

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

  1. class Solution {
  2.     public String addStrings(String num1, String num2) {
  3.         StringBuilder res = new StringBuilder(); // 返回结果
  4.         int p1 = num1.length() - 1; // 标记遍历到 num1 的位置
  5.         int p2 = num2.length() - 1; // 标记遍历到 num2 的位置
  6.         int carry = 0; // 进位
  7.         while (p1 >= 0 || p2 >= 0 || carry != 0) { // num1 没遍历完，或 num2 没遍历完，或进位不为 0
  8.             int digit1 = p1 >= 0 ? num1.charAt(p1) - '0' : 0; // 当前 num1 的取值
  9.             int digit2 = p2 >= 0 ? num2.charAt(p2) - '0' : 0; // 当前 num2 的取值
  10.             int add = digit1 + digit2 + carry; // 当前位置相加的结果
  11.             carry = add >= 10 ? 1 : 0; // 是否有进位
  12.             add = add >= 10 ? add - 10 : add; // 去除进位后留下的数字
  13.             res.append(add); // 把去除进位后留下的数字拼接到结果中
  14.             p1 --; // 遍历到 num1 的位置向左移动
  15.             p2 --; // 遍历到 num2 的位置向左移动
  16.         }
  17.         return res.reverse().toString(); // 把结果反转并返回
  18.     }
  19. }
class Solution {
public:
    string addStrings(string num1, string num2) {
        const int M = num1.size();
        const int N = num2.size();
        string res;
        int p1 = M - 1;
        int p2 = N - 1;
        int carry = 0;
        while (p1 >= 0 || p2 >= 0 || carry > 0) {
            int cur1 = p1 >= 0 ? num1[p1] - '0' : 0;
            int cur2 = p2 >= 0 ? num2[p2] - '0' : 0;
            int sum = cur1 + cur2 + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;
            res += to_string(sum);
            p1 --;
            p2 --;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

class Solution(object):
    def addStrings(self, num1, num2):
        p1 = len(num1) - 1
        p2 = len(num2) - 1
        res = ""
        carry = 0
        while p1 >= 0 or p2 >= 0 or carry > 0:
            digit1 = int(num1[p1]) if p1 >= 0 else 0
            digit2 = int(num2[p2]) if p2 >= 0 else 0
            sum = digit1 + digit2 + carry
            carry = 1 if sum >= 10 else 0
            sum = sum - 10 if sum >= 10 else sum
            res += str(sum)
            p1 -= 1
            p2 -= 1
        return res[::-1]

复杂度分析

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

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