每日一题-2020803

题目

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

注意：

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

题解

双指针，每一位置相加可以看成由 x, y, carry 进位组成。
时间复杂度 O(max(num1.length, num2.length))
空间复杂度 O(n)

object Solution {
    def addStrings(num1: String, num2: String): String = {
        var i = num1.length - 1
        var j = num2.length -1
        var carry = 0

        var ans = Seq[Int]()

        while (i >= 0 || j >=0 || carry !=0) {
          val x = if (i < 0) 0 else num1(i) - '0'
          val y = if (j < 0) 0 else num2(j) - '0'
          val result = x + y + carry
          carry = result / 10
          ans = ans :+ result % 10
          i -= 1
          j -= 1

        }

        ans.reverse.mkString("")
    }
}