LeetCode 题解工作台
字符串相加
给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库（比如 BigInteger ）， 也不能直接将输入的字符串转换为整数形式。 示例 1： 输入： num1 = "11", num2 = "123" 输出： "134"…
3
题型
8
代码语言
3
相关题
当前训练重点
简单 · 数学·string
答案摘要
我们用两个指针 和 分别指向两个字符串的末尾，从末尾开始逐位相加。每次取出对应位的数字 和 ，计算它们的和 $a + b + c$，其中 表示上一次相加的进位，最后将 $a + b + c$ 的个位数添加到追加到答案字符串的末尾，然后将 $a + b + c$ 的十位数作为进位 的值，循环此过程直至两个字符串的指针都已经指向了字符串的开头并且进位 的值为 。 最后将答案字符串反转并返回…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·string 题型思路
题目描述
给定两个字符串形式的非负整数 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 <= 104num1和num2都只包含数字0-9num1和num2都不包含任何前导零
解题思路
方法一：双指针
我们用两个指针 和 分别指向两个字符串的末尾，从末尾开始逐位相加。每次取出对应位的数字 和 ，计算它们的和 ，其中 表示上一次相加的进位，最后将 的个位数添加到追加到答案字符串的末尾，然后将 的十位数作为进位 的值，循环此过程直至两个字符串的指针都已经指向了字符串的开头并且进位 的值为 。
最后将答案字符串反转并返回即可。
时间复杂度 ，其中 和 分别是两个字符串的长度。忽略答案字符串的空间消耗，空间复杂度 。
以下代码还实现了字符串相减，参考 subStrings(num1, num2) 函数。
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j = len(num1) - 1, len(num2) - 1
ans = []
c = 0
while i >= 0 or j >= 0 or c:
a = 0 if i < 0 else int(num1[i])
b = 0 if j < 0 else int(num2[j])
c, v = divmod(a + b + c, 10)
ans.append(str(v))
i, j = i - 1, j - 1
return "".join(ans[::-1])
def subStrings(self, num1: str, num2: str) -> str:
m, n = len(num1), len(num2)
neg = m < n or (m == n and num1 < num2)
if neg:
num1, num2 = num2, num1
i, j = len(num1) - 1, len(num2) - 1
ans = []
c = 0
while i >= 0:
c = int(num1[i]) - c - (0 if j < 0 else int(num2[j]))
ans.append(str((c + 10) % 10))
c = 1 if c < 0 else 0
i, j = i - 1, j - 1
while len(ans) > 1 and ans[-1] == '0':
ans.pop()
if neg:
ans.append('-')
return ''.join(ans[::-1])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests your ability to simulate arithmetic operations without using built-in integer conversion.
- question_mark
Evaluates your understanding of string manipulation and handling of carries in addition.
- question_mark
Checks if you can handle edge cases like different string lengths and no leading zeros.
常见陷阱
外企场景- error
Failing to correctly handle carries, especially at the most significant digit.
- error
Not considering edge cases like one string being longer than the other.
- error
Incorrectly managing the case when the result has an additional carry at the end.
进阶变体
外企场景- arrow_right_alt
Add Strings for large numbers where the length of the strings exceeds typical integer limits.
- arrow_right_alt
Modify the problem to add multiple strings, not just two.
- arrow_right_alt
Optimize the solution to handle cases where both strings are of equal length.