Easy

题目描述

给定两个字符串形式的非负整数 num1 和 num2，返回 num1 和 num2 的和，也以字符串形式返回。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= num1.length, num2.length <= 10^4
  • num1 和 num2 都只包含数字
  • num1 和 num2 都不包含任何前导零，除了数字 0 本身

解题思路

这道题考查的是大数加法的模拟实现。由于题目限制不能直接转换为整数，我们需要模拟手工加法的过程。

解题思路：

  1. 双指针从后往前遍历：设置两个指针分别指向两个字符串的末尾，从低位到高位进行加法运算。

  2. 进位处理：维护一个进位变量 carry，每次计算当前位的和时，需要加上上一位的进位。当前位的值为 (num1[i] + num2[j] + carry) % 10，新的进位为 (num1[i] + num2[j] + carry) / 10。

  3. 长度不同的处理：当一个字符串遍历完后，另一个字符串可能还有剩余位数，需要继续处理剩余位数和进位。

  4. 结果构建：由于我们是从低位到高位计算的，需要将结果字符串反转，或者使用头插法构建结果。

  5. 最终进位：所有位都处理完后，如果还有进位，需要在最高位添加进位值。

这种方法时间复杂度为 O(max(m,n))，空间复杂度为 O(max(m,n))，其中 m 和 n 分别是两个字符串的长度。

代码实现

class Solution {
public:
    string addStrings(string num1, string num2) {
        string result = "";
        int carry = 0;
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int digit1 = i >= 0 ? num1[i] - '0' : 0;
            int digit2 = j >= 0 ? num2[j] - '0' : 0;
            
            int sum = digit1 + digit2 + carry;
            result = char(sum % 10 + '0') + result;
            carry = sum / 10;
            
            i--;
            j--;
        }
        
        return result;
    }
};

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        result = []
        carry = 0
        i = len(num1) - 1
        j = len(num2) - 1
        
        while i >= 0 or j >= 0 or carry:
            digit1 = int(num1[i]) if i >= 0 else 0
            digit2 = int(num2[j]) if j >= 0 else 0
            
            total = digit1 + digit2 + carry
            result.append(str(total % 10))
            carry = total // 10
            
            i -= 1
            j -= 1
        
        return ''.join(result[::-1])

public class Solution {
    public string AddStrings(string num1, string num2) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int i = num1.Length - 1;
        int j = num2.Length - 1;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int digit1 = i >= 0 ? num1[i] - '0' : 0;
            int digit2 = j >= 0 ? num2[j] - '0' : 0;
            
            int sum = digit1 + digit2 + carry;
            result.Insert(0, sum % 10);
            carry = sum / 10;
            
            i--;
            j--;
        }
        
        return result.ToString();
    }
}

var addStrings = function(num1, num2) {
    let result = "";
    let carry = 0;
    let i = num1.length - 1;
    let j = num2.length - 1;
    
    while (i >= 0 || j >= 0 || carry > 0) {
        const digit1 = i >= 0 ? parseInt(num1[i]) : 0;
        const digit2 = j >= 0 ? parseInt(num2[j]) : 0;
        
        const sum = digit1 + digit2 + carry;
        result = (sum % 10) + result;
        carry = Math.floor(sum / 10);
        
        i--;
        j--;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(max(m,n))m 和 n 分别是 num1 和 num2 的长度，需要遍历较长字符串的所有位
空间复杂度O(max(m,n))结果字符串的长度最多为 max(m,n) + 1

相关题目