题目地址(415. 字符串相加)

https://leetcode-cn.com/problems/add-strings/

题目描述

  1. 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
  3. 你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
  7. 示例 1：
  9. 输入：num1 = "11", num2 = "123"
  10. 输出："134"
  13. 示例 2：
  15. 输入：num1 = "456", num2 = "77"
  16. 输出："533"
  19. 示例 3：
  21. 输入：num1 = "0", num2 = "0"
  22. 输出："0"
  29. 提示：
  31. 1 <= num1.length, num2.length <= 104
  32. num1 和num2 都只包含数字 0-9
  33. num1 和num2 都不包含任何前导零

前置知识


公司

  • 暂无

思路

image.png
当前位相加的数= num1.charAt + num2.charAt + 进位
进位=sum /10
然后把 个位也就是sun%10放到数组
最后如果有进位就再加个1
最后把sb反转

关键点


代码

  • 语言支持：Java

Java Code:

  4. class Solution {
  5.     public String addStrings(String num1, String num2) {
  6.         StringBuilder sb = new StringBuilder();
  7.         int size1 = num1.length()-1;
  8.         int size2 = num2.length()-1;
  9.         int carry = 0;
  10.         while (size1 >= 0 || size2 >= 0) {
  11.             int sum1 = size1 >= 0 ? num1.charAt(size1) - '0' : 0;
  12.             int sum2 = size2 >= 0 ? num2.charAt(size2) - '0' : 0;
  13.             int sum = sum1 + sum2 + carry;
  14.             carry  = sum / 10;
  15.             sb.append(sum % 10);
  16.             size1--;
  17.             size2--;
  18.         }
  19.         if (carry == 1) {
  20.             sb.append(1);
  21.         }
  22.         return sb.reverse().toString();
  23.     }
  25. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：415. 字符串相加 - 图2#card=math&code=O%28n%29&id=c5Smb)
  • 空间复杂度：415. 字符串相加 - 图3#card=math&code=O%28n%29&id=zrFlb)