# 字符串乘法
![](../pictures/souyisou.png) 相关推荐: * [关于 Linux shell 你必须知道的](https://labuladong.gitbook.io/algo) * [回溯算法解题套路框架](https://labuladong.gitbook.io/algo) 读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目: [43.字符串相乘](https://leetcode-cn.com/problems/multiply-strings) **-----------** 对于比较小的数字,做运算可以直接使用编程语言提供的运算符,但是如果相乘的两个因数非常大,语言提供的数据类型可能就会溢出。一种替代方案就是,运算数以字符串的形式输入,然后模仿我们小学学习的乘法算术过程计算出结果,并且也用字符串表示。 ![](../pictures/%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/title.png) 需要注意的是,`num1` 和 `num2` 可以非常长,所以不可以把他们直接转成整型然后运算,唯一的思路就是模仿我们手算乘法。 比如说我们手算 `123 × 45`,应该会这样计算: ![](../pictures/%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/1.jpg) 计算 `123 × 5`,再计算 `123 × 4`,最后错一位相加。这个流程恐怕小学生都可以熟练完成,但是你是否能**把这个运算过程进一步机械化**,写成一套算法指令让没有任何智商的计算机来执行呢? 你看这个简单过程,其中涉及乘法进位,涉及错位相加,还涉及加法进位;而且还有一些不易察觉的问题,比如说两位数乘以两位数,结果可能是四位数,也可能是三位数,你怎么想出一个标准化的处理方式?这就是算法的魅力,如果没有计算机思维,简单的问题可能都没办法自动化处理。 首先,我们这种手算方式还是太「高级」了,我们要再「低级」一点,`123 × 5` 和 `123 × 4` 的过程还可以进一步分解,最后再相加: ![](../pictures/%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/2.jpg) 现在 `123` 并不大,如果是个很大的数字的话,是无法直接计算乘积的。我们可以用一个数组在底下接收相加结果: ![](../pictures/%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/3.jpg) 整个计算过程大概是这样,**有两个指针 `i,j` 在 `num1` 和 `num2` 上游走,计算乘积,同时将乘积叠加到 `res` 的正确位置**: ![](../pictures/%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/4.gif) 现在还有一个关键问题,如何将乘积叠加到 `res` 的正确位置,或者说,如何通过 `i,j` 计算 `res` 的对应索引呢? 其实,细心观察之后就发现,**`num1[i]` 和 `num2[j]` 的乘积对应的就是 `res[i+j]` 和 `res[i+j+1]` 这两个位置**。 ![](../pictures/%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/6.jpg) 明白了这一点,就可以用代码模仿出这个计算过程了: ```java string multiply(string num1, string num2) { int m = num1.size(), n = num2.size(); // 结果最多为 m + n 位数 vector