415. 字符串相加
题目描述
输入两个字符串 num1 和 num2，各自表示一个非负整数的十进制写法。
求这两个数的和，结果同样用十进制字符串返回。
不允许借助任何大数类库，也不允许先把整个字符串转换成整数类型再相加。需要按位模拟加法并处理进位。
示例 1
输入：num1 = "11", num2 = "123" 输出："134"
解释：11 + 123 = 134。
示例 2
输入：num1 = "456", num2 = "77" 输出："533"
解释：456 + 77 = 533，个位和十位都产生进位。
示例 3
输入：num1 = "0", num2 = "0" 输出："0"
解释：0 + 0 = 0。
数据范围
1 <= num1.length, num2.length <= 10^4num1和num2中只有字符0到9。- 两个字符串都没有前导零。
解题思路
模拟竖式加法：两个指针 i、j 从末位往前走，每一位取 a + b + carry，写下个位、进位留给下一位。某个数先走完就当作 0。只要还有数位或进位就继续，最后把结果反转。
为什么正确
处理完低 k 位后，res 倒过来是两数低 k 位之和的低 k 位，carry 是向第 k+1 位的进位。
复杂度分析
时间 O(max(m, n))；空间 O(max(m, n))（输出）。
易错点
循环条件忘记 carry 会丢掉最高位的进位，把 "9" + "1" 算成 "0"。用 res = d + res 从头部拼接在某些语言里是 O(n²)。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j, carry = len(num1) - 1, len(num2) - 1, 0
res = []
while i >= 0 or j >= 0 or carry:
a = int(num1[i]) if i >= 0 else 0
b = int(num2[j]) if j >= 0 else 0
carry, d = divmod(a + b + carry, 10)
res.append(str(d))
i, j = i - 1, j - 1
return ''.join(reversed(res))class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
StringBuilder res = new StringBuilder();
while (i >= 0 || j >= 0 || carry != 0) {
int a = i >= 0 ? num1.charAt(i) - '0' : 0;
int b = j >= 0 ? num2.charAt(j) - '0' : 0;
int s = a + b + carry;
carry = s / 10;
res.append(s % 10);
i--; j--;
}
return res.reverse().toString();
}
}class Solution {
public:
string addStrings(string num1, string num2) {
int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
string res;
while (i >= 0 || j >= 0 || carry) {
int a = i >= 0 ? num1[i] - '0' : 0;
int b = j >= 0 ? num2[j] - '0' : 0;
int s = a + b + carry;
carry = s / 10;
res.push_back('0' + s % 10);
i--, j--;
}
reverse(res.begin(), res.end());
return res;
}
};func addStrings(num1 string, num2 string) string {
i, j, carry := len(num1)-1, len(num2)-1, 0
res := []byte{}
for i >= 0 || j >= 0 || carry > 0 {
a, b := 0, 0
if i >= 0 {
a = int(num1[i] - '0')
}
if j >= 0 {
b = int(num2[j] - '0')
}
s := a + b + carry
carry = s / 10
res = append(res, byte('0'+s%10))
i, j = i-1, j-1
}
for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
res[l], res[r] = res[r], res[l]
}
return string(res)
}var addStrings = function(num1, num2) {
let i = num1.length - 1, j = num2.length - 1, carry = 0;
const res = [];
while (i >= 0 || j >= 0 || carry) {
const a = i >= 0 ? +num1[i] : 0;
const b = j >= 0 ? +num2[j] : 0;
const s = a + b + carry;
carry = Math.floor(s / 10);
res.push(s % 10);
i--; j--;
}
return res.reverse().join('');
};function addStrings(num1: string, num2: string): string {
let i = num1.length - 1, j = num2.length - 1, carry = 0;
const res: number[] = [];
while (i >= 0 || j >= 0 || carry) {
const a = i >= 0 ? +num1[i] : 0;
const b = j >= 0 ? +num2[j] : 0;
const s = a + b + carry;
carry = Math.floor(s / 10);
res.push(s % 10);
i--; j--;
}
return res.reverse().join('');
}