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

坚持用 清晰易懂的图解 + 代码语言，让每个知识点变得简单！
🚀呆头个人主页详情
🌱 呆头个人Gitee代码仓库
📌 呆头详细专栏系列
座右铭： “不患无位，患所以立。”

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

• 前言
• • 题目描述
  • 示例
  • 题目分析
  • 解题思路
  • 代码实现
  • 代码详解
  • 算法复杂度分析
  • 优化点
  • 总结
  • 相关题目推荐

前言

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

🔍 专栏初衷：

• 用清晰的图解 + 多语言代码（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\"

题目分析

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

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

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

解题思路

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

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

代码实现

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

代码详解

1. 初始化：

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

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

2. 设置指针和进位：

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

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

3. 逐位相加：

   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补充
   • 计算当前位的值和新的进位
   • 将当前位的结果添加到结果字符串

4. 处理最终进位：

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

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

5. 反转结果：

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

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

算法复杂度分析

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

优化点

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

总结

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

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

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

相关题目推荐

• LeetCode 2. 两数相加
• LeetCode 43. 字符串相乘
• LeetCode 66. 加一
• LeetCode 67. 二进制求和
• LeetCode 989. 数组形式的整数加法

📢 如果你也喜欢这种“不呆头”的技术风格：
👁️ 【关注】 看一个非典型程序员如何用野路子解决正经问题
👍 【点赞】 给“不写八股文”的技术分享一点鼓励
🔖 【收藏】 把这些“奇怪但有用”的代码技巧打包带走
💬 【评论】 来聊聊——你遇到过最“呆头”的 Bug 是啥？
🗳️ 【投票】 您的投票是支持我前行的动力
技术没有标准答案，让我们一起用最有趣的方式，写出最靠谱的代码！ 🎮💻