描述

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。

示例 1:

输入:num1 = "11", num2 = "123"
输出:"134"

示例 2:

输入:num1 = "456", num2 = "77"
输出:"533"

示例 3:

输入:num1 = "0", num2 = "0"
输出:"0"

思路

这道题首先不可以将其转为整数来进行计算的,需要在字符串基础上进行相加。不过就算是基于字符串但是思想是不变的,大家可以想一下,两个整数相加是不是要从最后一位开始相加,如果相加结果小于10,那么该结果就作为最终结果的最后一位,如果大于10,就需要向前进一位,这个进位需要参与到高一位的运算当中。 alt 所以说这道题的关键点就是在于进位的处理上。

AC 代码

class Solution {
    public String addStrings(String num1, String num2) {
        // 如果其中一个为空就返回另一个字符串
        if (num1 == null) {
            return num2;
        } else if (num2 == null) {
            return num1;
        }

        StringBuffer res = new StringBuffer();
        // 双指针 index1:num1 的坐标,index2:num2 的坐标
        int index1 = num1.length() - 1;
        int index2 = num2.length() - 1;
        int carry = 0; // 进位,默认为 0
        while (index1 >= 0 || index2 >= 0 || carry > 0) {
            int value1 = index1 >= 0 ? num1.charAt(index1) - '0' : 0;
            int value2 = index2 >= 0 ? num2.charAt(index2) - '0' : 0;
            int sum = value1 + value2 + carry;
            carry = sum / 10; // 计算进位
            sum = sum % 10; // 计算该位置的值
            res.append(sum);
            index1 --;
            index2 --;
        }
        return res.reverse().toString();
    }
}
  • 时间复杂度:O(Max(M, N)), M、N 为两个字符串的长度
  • 空间复杂度:O(1),没有使用额外空间。

最后

这道题还是蛮简单的,但是确实面试频率很高的一道题,这道题的升级版就是 字符串相乘,该题难度要大一些,之后我也会出其对应的题解的。

大家有空可以来我的公众号 蘑菇睡不着 交流一下。