lc415. 字符串相加（高精度加法&双指针）

给定两个字符串形式的非负整数 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) {
        StringBuffer res = new StringBuffer();
        int carry = 0;
        int i = num1.length()-1, j = num2.length()-1;
        while(i >= 0 || j >= 0){
            int sum = carry;
            sum += i >= 0 ? num1.charAt(i--)-'0' : 0;
            sum += j >= 0 ? num2.charAt(j--)-'0' : 0;
            res.append(sum % 10);
            carry = sum / 10;
        }
        if(carry > 0) res.append(1);
        return res.reverse().toString();
    }
}

高精度加法

class Solution {
    List<Integer>a;
    List<Integer>b;
    public String addStrings(String num1, String num2) {
        a = new ArrayList<>();
        b = new ArrayList<>();
        for(int i = num1.length()-1; i >= 0; --i)a.add(num1.charAt(i)-'0');
        for(int i = num2.length()-1; i >= 0; --i)b.add(num2.charAt(i)-'0');
        List<Integer> res = add(a,b);
        String s = "";
        for(int i = res.size()-1; i >= 0; --i) s += res.get(i);
        return s;
    }
    public List<Integer> add(List<Integer> a, List<Integer> b){
        List<Integer> res = new ArrayList<>();
        int carry = 0;
        for(int i = 0; i < a.size() || i < b.size(); ++i){
            int sum = carry;
            sum += i < a.size() ? a.get(i) : 0;
            sum += i < b.size() ? b.get(i) : 0;
            res.add(sum % 10);
            carry = sum / 10; 
        }
        if(carry > 0) res.add(1);
        return res;
    }
}