【常见面试算法】大数相加（字符串相加）

问题

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

注意：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

准备变量carry表示进位，index1为num1的指针，index2为num2的指针。

算法执行步骤如下：

1. 双指针都合法，依次向前移动并计算结果和进位（记得每次用完进位把进位置0）；
2. 某个字符串已经遍历完毕，接下来遍历剩下的那个，步骤与1相似；
3. 字符串遍历完成，但进位不为零，需要在输出前插入进位。

class Solution {
    public String addStrings(String num1, String num2) {
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        int index1 = num1.length() - 1;
        int index2 = num2.length() - 1;

        while (index1 >= 0 && index2 >= 0) {
            int tmp = num1.charAt(index1--) - '0' + num2.charAt(index2--) - '0' + carry;
            carry = 0;
            if (tmp >= 10) {
                carry = tmp / 10;
            }
            sb.insert(0,tmp % 10);
        }
        while (index1 >= 0) {
            int tmp = num1.charAt(index1--) - '0' + carry;
            carry = 0;
            if (tmp >= 10) {
                carry = tmp / 10;
            }
            sb.insert(0,tmp % 10);
        }
        while (index2 >= 0) {
            int tmp = num2.charAt(index2--) - '0'  + carry;
            carry = 0;
            if (tmp >= 10) {
                carry = tmp / 10;
            }
            sb.insert(0,tmp % 10);
        }
        if (carry != 0) {
            sb.insert(0,carry);
        }

        return sb.toString();
    }
}