关键词：竖式加法

1. 题目描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

提示：

  1. num1 和num2 的长度都小于 5100
  2. num1 和num2 都只包含数字 0-9
  3. num1 和num2 都不包含任何前导零
  4. 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

    2. 解题思路

    这里我们模拟竖式加法，遍历两个字符串，从个位开始将两个数相加。定义一个temp来保存两个数的和。将temp与10取余，得到的值加在结果res中，如果有进位，就将temp赋值为1，方便前面的位相加。最后判断相加完之后，temp是否等于1，如果是就进一位，在结果前面加一个1。

复杂度分析：

  • 时间复杂度: O(max(len1, len2))，其中len1和len2分别是num1和num2的长度，竖式加法的次数取决于较大数的位数。

  • 空间复杂度: O(1)，除答案外只需要常数空间存放若干变量。

    3. 代码实现

    1. /**
    2. * @param {string} num1
    3. * @param {string} num2
    4. * @return {string}
    5. */
    6. var addStrings = function(num1, num2) {
    7.   let len1 = num1.length, len2 = num2.length, temp = 0, res = "";
    9.   while(len1 || len2){
    10.       if(len1){
    11.           temp += +num1[--len1]
    12.       }
    13.       if(len2){
    14.           temp += +num2[--len2]
    15.       }
    16.       res = temp % 10 + res
    17.       temp > 9 ? temp = 1 : temp = 0
    18.   } 
    19.   if(temp){
    20.       res = 1 + res
    21.   }
    22.   return res
    23. };

    4. 提交结果

    image.png