开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 面试必会的算法题——求加法 -> 正文阅读

[数据结构与算法]面试必会的算法题——求加法

作者：负雪明烛
id： fuxuemingzhu
公众号：负雪明烛
本文关键词：求加法，两数相加，两数之和，数字相加，十进制加法，链表相加，字符串相加

大家好，我是「负雪明烛」。7 年刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。持续在写作算法、面试方面的精彩内容。

关注我的公众号， 你将不会错过我的精彩动画题解、面试题分享、组队刷题活动。

今天继续更新「面试必会的算法题」系列文章的第二篇——「求加法」。

面试必会的算法题系列文章：

面试必会的算法题——前缀和

前言

加法是我们上小学的时候开始学习的第一种数学运算。

在算法题中，「求加法」问题大多考察「列竖式」求和。

题目中，「两数之和」通常与其他形式表示的数字结合起来：

两个字符串形式的数字相加（第 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)含义：
1. 字符串 num1 和 num2 只要有一个没遍历完，那么就继续遍历；
2. 如果字符串 num1 和 num2 都遍历完了，但是最后留下的进位 carry != 0，那么需要把进位也保留到结果中。
取 digit 的时候，如果字符串 num1 和 num2 中有一个已经遍历完了（即 $p 1 < 0$ 或者 $p 2 < 0$ ），则认为 num1 和 num2 的对应位置是 $0$ 。

代码

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

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(); // 把结果反转并返回
    }
}

复杂度分析

时间复杂度： $O (m a x (M, N))$ ， $M$ 和 $N$ 分别是字符串 num1 和 num2 的长度；
空间复杂度： $O (1)$ ，只使用了常数的空间。

链表形式的数字相加

题目

以 2. 两数相加为例。

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0ix60xwV-1635469626318)(https://picture-bed-1251805293.cos.ap-beijing.myqcloud.com/202110280842726.png)]
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

在这里插入图片描述

示例 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;
    }
}