415. 字符串相加

难度: 简单

来源: 每日一题 2023.07.17

---

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

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

 
示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

示例 2：

输入：num1 = "456", num2 = "77"
输出："533"

示例 3：

输入：num1 = "0", num2 = "0"
输出："0"

提示：

1 <= num1.length, num2.length <= 104
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零

class Solution {
    public String addStrings(String num1, String num2) {

    }
}

分析与题解

---

• 模拟算法+双指针

  这个题我们只需模拟一下数学算法即可. 也就是说我们模拟一下数学中的加法过程即可.

  我们需要定义两个指针,分别指向 num1 和 num2 的尾部位置,然后通过移动逐位相加即可.

  相比于官方的全部遍历的方式(num1 和 num2 谁长遍历谁),示例代码如下所示.

  注意: carryNumber 代表着进位

  while(firstIndex >= 0 || secondeIndex >= 0 || carryNumber > 0) 
  

  时间复杂度会成为 O(max(num1.length, num2.length))

  但是我这里做了一部分优化, 谁短遍历谁,谁有剩余直接添加的方式.

  注意: carryNumber 代表着进位

      while((firstIndex >= 0 && secondeIndex >= 0) || carryNumber > 0){
          // ...
      }
      if (firstIndex >=0) {
          // 添加num1的剩余
      }
      if (secondeIndex >=0) {
          // 添加num2的剩余
      }
  
  

  时间复杂度会成为 O(min(num1.length, num2.length))

  最终,整个解题过程如下所示.

  class Solution {
      public String addStrings(String num1, String num2) {
          int firstIndex = num1.length() - 1;
          int secondeIndex = num2.length() - 1;
          int carryNumber = 0;
          String result = "";
          while((firstIndex >= 0 && secondeIndex >= 0) || carryNumber > 0) {
              int sum = 0;
              if (firstIndex >= 0) {
                  sum += (num1.charAt(firstIndex) - '0');
                  firstIndex--;
              }
              if (secondeIndex >= 0) {
                  sum += (num2.charAt(secondeIndex) - '0');
                  secondeIndex--;
              }
              if (carryNumber > 0) {
                  sum += carryNumber;
                  carryNumber = 0;
              }
              if (sum >= 10) {
                  carryNumber = sum/10;
                  result = sum%10 + result;
              } else {
                  result = sum + result;
              }
          }
          if (firstIndex >=0) {
              result = num1.substring(0, firstIndex + 1) + result;
          }
          if (secondeIndex >=0) {
              result = num2.substring(0, secondeIndex + 1) + result;
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(min(num1.length, num2.length))
  • 空间复杂度: O(1)

  结果如下所示.