面试必会的算法题——求加法
The following article is from 负雪明烛 Author 负雪明烛
出品 | 负雪明烛 （ID：fuxuemingzhu_writing）
已获得原公众号的授权转载前言
加法是我们上小学的时候开始学习的第一种数学运算。
在算法题中，「求加法」问题大多考察「列竖式」求和。
题目中，「两数之和」通常与其他形式表示的数字结合起来：
两个字符串形式的数字相加（第 415 题） 两个链表形式的数字相加（第 2 、445、369 题） 数组形式的数字相加（第 66 、989题） 两个二进制形式的数字相加（第 67 题）
做法都是非常类似的，本质是在考察各种数据表示形式：字符串，链表，数组，二进制。
我们只要掌握了用「列竖式」求「两数之和」的方法，这类题目全都可以秒杀。
十进制加法
我们先回顾一下十进制加法的计算过程：
使用「竖式」计算十进制的加法的方式：
两个「加数」的右端对齐； 从最右侧开始，从右向左依次计算对应的两位数字的和，如果有进位需要加上进位。如果和大于等于 10，则把和的个位数字计入结果，并向前面进位； 重复步骤 2； 当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中。
在实现中需要注意的有：
不可以把链表/字符串表示的「加数」先转化成 int型数字再求和，因为可能溢出；两个「加数」的字符串长度可能不同； 在最后，如果进位 carry不为 0，那么最后需要计算进位。注意 结果数字 是否为低位结果在前，根据题目要求判断最后是否要反转结果。
例题
字符串形式的数字相加
题目
以 415. 字符串相加 为例。
给定两个字符串形式的非负整数
num1和num2，计算它们的和并同样以字符串形式返回。你不能使用任何内建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = "11", num2 = "123"
输出："134"
题目要我们求两个字符串形式表示的数字相加，按照「列竖式」的方法进行求解即可。
代码说明
while (p1 >= 0 || p2 >= 0 || carry != 0)含义：字符串 num1和num2只要有一个没遍历完，那么就继续遍历；如果字符串 num1和num2都遍历完了，但是最后留下的进位carry != 0，那么需要把进位也保留到结果中。取 digit的时候，如果字符串num1和num2中有一个已经遍历完了（即 或者 ），则认为num1和num2的对应位置是 。
代码
该代码可以作为「求加法」的模板。
Java 代码如下：
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder res = new StringBuilder(); // 返回结果
int p1 = num1.length() - 1; // 标记遍历到 num1 的位置
int p2 = num2.length() - 1; // 标记遍历到 num2 的位置
int carry = 0; // 进位
while (p1 >= 0 || p2 >= 0 || carry != 0) { // num1 没遍历完，或 num2 没遍历完，或进位不为 0
int digit1 = p1 >= 0 ? num1.charAt(p1) - '0' : 0; // 当前 num1 的取值
int digit2 = p2 >= 0 ? num2.charAt(p2) - '0' : 0; // 当前 num2 的取值
int add = digit1 + digit2 + carry; // 当前位置相加的结果
carry = add >= 10 ? 1 : 0; // 是否有进位
add = add >= 10 ? add - 10 : add; // 去除进位后留下的数字
res.append(add); // 把去除进位后留下的数字拼接到结果中
p1 --; // 遍历到 num1 的位置向左移动
p2 --; // 遍历到 num2 的位置向左移动
}
return res.reverse().toString(); // 把结果反转并返回
}
}
复杂度分析
时间复杂度：， 和 分别是字符串 num1和num2的长度；空间复杂度：，只使用了常数的空间。
链表形式的数字相加
题目
以 2. 两数相加 为例。
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
image-20211028084256433 示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
分析
本题中的两个链表表示的数字是个位在前，高位在后。
所以，我们可以从两个链表的开头开始同时向后遍历，模拟「列竖式」求加法的过程。
代码
Java 代码如下：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int i1 = l1 != null ? l1.val : 0;
int i2 = l2 != null ? l2.val : 0;
int add = i1 + i2 + carry;
carry = add >= 10 ? 1 : 0;
add = add >= 10 ? add - 10 : add;
cur.next = new ListNode(add);
cur = cur.next;
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
}
return dummy.next;
}
}
复杂度分析
时间复杂度：， 和 分别是链表 a和b的长度；空间复杂度：，只使用了常数的空间。
类似题目
看完本文，你可以解决以下题目：
415. 字符串相加 2. 两数相加 445. 两数相加 II 369. 给单链表加一 66. 加一 989. 数组形式的整数加法 67. 二进制求和
总结
「求加法」系列题目都不难，其实就是「列竖式」计算。 需要注意的是： while循环结束条件；遍历两个「加数」不要越界； 进位。
参考：
https://leetcode.com/problems/add-two-numbers/solution/
推荐阅读：
每日打卡赢积分兑换书籍入口