字符串中等1 种解法
#43字符串相乘
不使用大整数类型，也不把完整输入转换为整数，返回两个非负整数字符串的乘积。
#数学#字符串#模拟
原题
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
提示：
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
解题主线
- num1[i] × num2[j] 的个位累加到 result[i+j+1]，进位累加到 result[i+j]。
- 长度为 m、n 的乘积最多占 m+n 位。
解法 1：竖式乘法数组
逐对相乘并在固定位置完成累加和进位，最后跳过结果的前导零。
-
时间复杂度： O(mn)
-
空间复杂度： O(m + n)
final class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) return "0";
// digits[i + j + 1] 接收当前乘积的个位，左邻位置累加进位。
int[] digits = new int[num1.length() + num2.length()];
for (int i = num1.length() - 1; i >= 0; i--) {
int first = num1.charAt(i) - '0';
for (int j = num2.length() - 1; j >= 0; j--) {
int second = num2.charAt(j) - '0';
// 当前位置先叠加历史进位，再同步写回个位与更高位进位。
int sum = digits[i + j + 1] + first * second;
digits[i + j + 1] = sum % 10;
digits[i + j] += sum / 10;
}
}
StringBuilder result = new StringBuilder(digits.length);
int index = digits[0] == 0 ? 1 : 0;
while (index < digits.length) result.append(digits[index++]);
return result.toString();
}
}实现提示
- 明确排除旧文件中会发生 int 溢出的 atoi 后直接相乘方案。
边界与易错点
- 旧 multiply1 先调用 atoi 再做 int 乘法，会截断或溢出，不能通过题目大数用例，因此不作为推荐解法。
- 结果数组最高位可能为 0，构造字符串时只跳过前导零，不能丢掉乘积 0。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q043_AtioII_multiply.java