[数据结构与算法]大数加法（java）

大数加法
以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

数据范围：length<10000，字符串仅由’0’~‘9’构成
要求： 空间复杂度 O(1)（仅在传入字符串上操作）,时间复杂度 O(n)

示例1
输入：
“1”,“99”
返回值：
“100”
说明：
1+99=100

示例2
输入：
“114514”,""
复制
返回值：
“114514”

思路：从字符串后面往前加，每次相加一次，下标减1，直到某字符串消耗完 就用0来加。

public class BigNumAdd {
   
    public static String solve (String s, String t) {
         StringBuilder stringBuilder = new StringBuilder();
         //x,y从两个字符串的最后一数字开始，jinwei是进位
         int i=s.length()-1,j=t.length()-1,jinwei=0;
         //每用掉一次就i--,y--,当某个字符串先没有数了 就用0来加。
        //可能两边都没有数了，但是jinwei还是>0，所以还要进来一次
         while (i>=0 || j>=0 || jinwei>0){
             int x=i<0?0:s.charAt(i--)-'0';
             int y=j<0?0:t.charAt(j--)-'0';
             int sum =x+y+jinwei;
             // 加入sum个位上的数，每次从头部插入就不用逆序返回了
             stringBuilder.insert(0,sum%10);
             //进位 sum不满10就为0
             jinwei=sum/10;
         }
         return stringBuilder.toString();
    }
}