跳至主要內容

415. 字符串相加


415. 字符串相加open in new window

🟢   🔖  数学 字符串 模拟  🔗 力扣open in new window LeetCodeopen in new window

题目

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.

题目大意

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

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

解题思路

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

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

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

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

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

复杂度分析

  • 时间复杂度O(max(m, n)),其中 mn 是两个字符串的长度。需要遍历两个字符串的每一位。
  • 空间复杂度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两数相加open in new window[✓]递归 链表 数学
43字符串相乘open in new window[✓]数学 字符串 模拟
989数组形式的整数加法open in new window数组 数学