【LeetCode 415】—字符串相加算法详解

我不是呆头

发布于 2025-12-20 12:40:19

930

🚀 你好，欢迎来到《编程闯关记》！ 这里是算法与数据结构的实战基地，也是你从“暴力解法”到“最优解”的进化场。

🔍 专栏初衷：

用清晰的图解 + 多语言代码（Python/Java/C++/C），拆解每道题背后的逻辑。
不只讲“怎么做”，更讲“为什么”——从题目分析、边界条件到复杂度优化。
适合想夯实基础或突击面试的你，尤其针对LeetCode/牛客高频题！

💡 如何使用本专栏： 1️⃣ 先独立思考：尝试自己写出第一版代码（哪怕很烂）。 2️⃣ 对比解法：看看我的思路和你的差异，吸收优化技巧。 3️⃣ 举一反三：每篇末尾会附相似题目链接，趁热打铁。

📌 坚持打卡：算法没有捷径，但正确的方法能让你少走弯路。每天15分钟，和我一起用代码雕刻思维！

题目描述

力扣链接直达----------请点击

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

你不能使用任何内建的大数类型（比如 BigInteger）或直接将输入的字符串转换为整数形式。

示例

示例 1：

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

示例 2：

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

示例 3：

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

题目分析

这道题要求我们实现两个字符串形式的数字相加，并返回字符串结果。由于输入的数字可能非常大，超出常规整数类型的范围，所以不能直接转换为整数进行计算。

这个问题本质上是在模拟我们小学学习的竖式加法运算过程：

从最低位（个位）开始，逐位相加
处理进位情况
最后可能需要在最高位增加一个进位

解题思路

我们可以采用以下步骤解决这个问题：

从两个字符串的末尾开始遍历（即从个位开始）
对应位置的数字相加，再加上可能的进位
计算当前位的结果和新的进位
将当前位的结果添加到结果字符串中
遍历结束后，检查是否还有进位，如果有则添加到结果中
由于我们是从低位到高位计算的，最后需要将结果字符串反转

代码实现

class Solution {
public:
    string addStrings(string num1, string num2) {
        string str;
        str.reserve(max(num1.size(),num2.size())+1);
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int carry = 0;
        while(end1 >= 0 || end2 >= 0)
        {
            int x1 = end1 >= 0 ? num1[end1--] - '0' : 0;
            int x2 = end2 >= 0 ? num2[end2--] - '0' : 0;
            
            int val = x1 + x2 + carry;
            carry = val / 10;
            val = val % 10;

            str +=('0' + val);
        }

        if(carry ==1 )
        {
            str += '1' ;
           
        }
         reverse(str.begin(),str.end());
         return str;
    }
};

代码详解

初始化：

string str;
str.reserve(max(num1.size(),num2.size())+1);

我们预先为结果字符串分配足够的空间，最大长度为两个输入字符串中较长的那个加1（可能的进位）。

设置指针和进位：

int end1 = num1.size() - 1;
int end2 = num2.size() - 1;
int carry = 0;

end1和end2分别指向两个字符串的末尾（最低位），carry用于记录进位。

逐位相加：

while(end1 >= 0 || end2 >= 0)
{
    int x1 = end1 >= 0 ? num1[end1--] - '0' : 0;
    int x2 = end2 >= 0 ? num2[end2--] - '0' : 0;
    
    int val = x1 + x2 + carry;
    carry = val / 10;
    val = val % 10;

    str +=('0' + val);
}

循环条件是只要还有任一字符串未处理完
从字符转换为数字：num[i] - '0'
如果某个字符串已经处理完，对应位置用0补充
计算当前位的值和新的进位
将当前位的结果添加到结果字符串

处理最终进位：

if(carry == 1)
{
    str += '1';
}

如果最后还有进位，需要在结果中添加一个’1’。

反转结果：

reverse(str.begin(),str.end());

因为我们是从低位到高位构建结果的，所以最后需要反转字符串。

算法复杂度分析

时间复杂度：O(max(n, m))，其中n和m分别是两个输入字符串的长度。我们需要遍历两个字符串各一次。
空间复杂度：O(max(n, m))，需要存储结果字符串。

优化点

使用reserve()预分配内存，避免多次内存重新分配，提高效率。
直接在循环中处理字符到数字的转换，减少了额外的转换步骤。
使用+=运算符追加字符，简化了代码。

总结

这道题是一个经典的大数加法问题，通过模拟人工计算的过程，我们可以实现任意长度的数字相加。关键点在于：

从低位到高位逐位计算
正确处理进位
最后反转结果

这种方法不仅可以用于解决本题，还可以扩展到其他需要处理大数运算的场景，如大数减法、乘法等。