本文转载自微信公众号安姐《三分钟学前端》。转载本文请联系三分钟学习前端公众号。给定两个表示为字符串的非负整数num1和num2，返回也表示为字符串的num1和num2的乘积。示例1：输入：num1="2",num2="3"输出："6"示例2：输入：num1="123",num2="456"输出："56088"解释：num1和num2的长度小于110。num1和num2仅包含数字0-9。num1和num2都不是从零开始的，数字0本身除外。它不能使用任何标准库的大数字类型（例如BigInteger）或直接将输入转换为整数来处理。解法一：常规解法从右到左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，然后将每次得到的结果累加。另外，当乘数的每一位和被乘数的高位（不是最低位）相乘时，注意低位补'0'letmultiply=function(num1,num2){if(num1==="0"||num2==="0")return"0"//用于保存计算结果letres="0"//将num2逐位乘以num1for(leti=num2.length-1;i>=0;i--){letcarry=0//保存第i位数字乘以num1的结果lettemp=''//补0for(letj=0;j=0||carry!=0;j--){letn1=j<0?0:num1.charAt(j)-'0'letproduct=(n1*n2+carry)%10temp+=productcarry=Math.floor((n1*n2+carry)/10)}//计算当前结果和新计算的结果作为新结果res=addStrings(res,Array.prototype.slice.call(temp).reverse().join(""))}returnres}letaddStrings=function(num1,num2){leta=num1.length,b=num2.length,result='',tmp=0while(a||b){a?tmp+=+num1[--a]:''b?tmp+=+num2[--b]:''result=tmp%10+resultif(tmp>9)tmp=1elsetmp=0}if(tmp)result=1+resultreturnresult}复杂度分析：时间复杂度：O(max(m*n,n*n))空间复杂度度：O(m+n)解法二：垂直乘法（优化）两个数M和N相乘的结果可以是由N的各位数乘以M得到，如下图：依次计算num1的各位数乘以num2的和，将得到的所有和按对应位置相加得到num1*num2的结果letmultiply=function(num1,num2){if(num1==='0'||num2==='0')return"0"//用来保存计算结果letres=[]//从每个位数开始逐位相乘for(leti=0;i=10&&(res[i+j+1]=res[i+j+1]?res[i+j+1]+Math.floor(pos/10):Math.floor(pos/10)));}}returnres.reverse().join("");}复杂度分析：时间co复杂度：O(m*n)空间复杂度：O(m+n)
