相加求和问题 | LeetCode

文章目录[隐藏]

415 字符串相加
2 两数相加

本篇文章分享 LeetCode 中两道关于求和的题目，难度适中。

第一题是 LeetCode.415 简单·字符串相加

另一题是 LeetCode.2 中等·两数相加

这两道题目呢，一道是字符串类型的，一道是链表类型的，两道题目非常相似，思路也差不多。其实只要 415 的 字符串相加 写出来，就会发现第 2 题的难度并不算是中等 🤣。

好的，下边来上菜~

415 字符串相加

给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和。

提示：

num1 和 num2 的长度都小于 5100

num1 和 num2 都只包含数字 0-9

num1 和 num2 都不包含任何前导零

不能使用任何內建 BigInteger 库，也不能直接将输入的字符串转换为整数形式

题目中没有给出示例，但是根据题目描述的意思，我们可以知道，应该是这个样子的：

Input: "123" ，"28"

Output: "151"

Reason: 123 + 28 = 151

首先拿到这个题目，我们可以思考加法运算的基本法则：从个位开始运算，两两相加+进位，大于 10 需要进位。有了这个规则，我们就可以确定思路了。

从末尾开始运算，进行加减
定义一个变量存储进位，暂且命名为 carry
对于字符串长度进行统一化（怎么统一呢？补零即可。 123 + 23 = 123 + 023 这个样子）
在不将字符串转为数字的情况下如何进行？（我们可以利用字符间的大小值差距进行运算）

OK，分析之后，我们便可以写出来 Solution 了 👇

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1;
        int carry = 0;  // 进位
        StringBuffer sb = new StringBuffer();

        // 从末尾开始遍历，当存在字符串未遍历完或进位不为 0 进入循环
        while(i &gt; -1 || j &gt; -1 || carry != 0){
            // 判断是否越界，若越界则用 0 进行填充
            int first = (i &gt; -1) ? num1.charAt(i) - &#039;0&#039; : 0;
            int second = (j &gt; -1) ? num1.charAt(j) - &#039;0&#039; : 0;
            int sum = first + second + carry;   // 总和为 两数相加再加上进位
            carry = sum / 10;                   // 计算本次相加的进位
            sb.append(sum % 10);                // 将计算结果拼接到 stringbuffer 末尾
            // 移动指针
            i--;
            j--;
        }
        // 由于上述得到的 StringBuffer 结果实际为反过来的运算结果，所以在返回前需要执行 reverse() 进行反转
        return sb.reverse().toString();
    }
}

对于该解法，我们可以计算出它的时间空间复杂度：

时间复杂度：O(max(len1, len2)). len1 代表 num1 的长度，len2 代表 num2 的长度
空间复杂度：O(n). 因为过程中用到了 StringBuffer 进行存储，消耗了对应长度的空间

2 两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

字节跳动曾使用过该题原题

有了上一题目的基础，我们发现，这道题实际上是一样的嘛，只不过将字符串换作了链表，而该链表也是经过了反序的链表，并且根据题目给出的示例，我们完全可以直接从头开始运算。在整个计算过程中我们需要注意的点依旧是：

计算过程中的进位
链表的长度及对空节点的处理

我们依旧采取 carry 进行存储进位，并将短链表补齐长度，所填充的节点用 0 进行运算。

好，下边让我们献上代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();       // 定义返回值
        ListNode curr = result;                 // 定义指针指向链表当前节点
        int carry = 0;

        // 当链表未遍历完成或进位不为 0 的时候，执行循环
        while(l1 != null || l2 != null || carry != 0){
            int first = (l1 != null) ? l1.val : 0;
            int second = (l2 != null) ? l2.val : 0;
            int sum = first + second + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);

            // 移动链表指针
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
            curr = curr.next;
        }
        return result.next;
    }
}

对于该解法，我们可以计算出它的时间空间复杂度：