415. 字符串相加

🟢   🔖  数学 字符串 模拟  🔗 LeetCode

题目

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

Example 1:

Input: num1 = "11", num2 = "123"

Output: "134"

Example 2:

Input: num1 = "456", num2 = "77"

Output: "533"

Example 3:

Input: num1 = "0", num2 = "0"

Output: "0"

Constraints:

• 1 <= num1.length, num2.length <= 10^4
• num1 and num2 consist of only digits.
• num1 and num2 don't have any leading zeros except for the zero itself.

题目大意

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

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

解题思路

1. 反向遍历：从字符串的最后一位开始遍历，以便处理进位。这样可以从最低位开始相加，符合数学加法的规则。

2. 逐位相加：逐位相加对应位置的数字。对于每一位，计算两个字符的数值，进行相加并考虑进位。

3. 进位处理：如果某一位的和大于或等于 10，则需要向下一位传递进位（carry），并更新当前位的结果。

4. 处理剩余位和进位：遍历结束后，如果还有进位，则需要在结果字符串前添加进位。

5. 结果构建：使用字符串拼接的方式构建最终结果，注意结果需要反向，因为我们是从低位到高位计算的。

复杂度分析

• 时间复杂度：O(max(m, n))，其中 m 和 n 是两个字符串的长度。需要遍历两个字符串的每一位。
• 空间复杂度：O(max(m, n))，用于存储结果字符串。

代码

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
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 x1 = i >= 0 ? num1[i] - '0' : 0; // num1 的当前位
		const x2 = j >= 0 ? num2[j] - '0' : 0; // num2 的当前位
		const sum = x1 + x2 + carry; // 当前位的和

		result = (sum % 10) + result; // 结果的当前位，注意拼接方向
		carry = Math.floor(sum / 10); // 更新进位

		i--; // 移动到下一位
		j--;
	}

	return result; // 返回最终结果
};

相关题目

题号	标题	题解	标签	难度
2	两数相加	[✓]	递归 链表 数学
43	字符串相乘	[✓]	数学 字符串 模拟
989	数组形式的整数加法		数组 数学