415.字符串相加

题目:415.字符串相加

给定两个字符串形式的非负整数 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 <= 10^4
num1 和 num2 都只包含数字 0-9
num1 和 num2 都不包含任何前导零

思路

模拟手动加法的过程，从两个字符串的末尾开始逐位相加，并处理可能出现的进位情况。

1. 从末尾逐位相加：从两个字符串的最后一位开始，逐位相加。
2. 进位处理：通过 sum / 10 来处理进位，通过 sum % 10 得到当前位的值。
3. 循环终止条件：当两个数字都处理完并且没有进位时，循环终止。
4. 反转结果：由于我们是从低位开始加的，因此需要在最终输出时将结果反转。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public String addStrings(String num1, String num2) {
    StringBuilder result = new StringBuilder();
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    // 进位
    int carry = 0;
    while (i >= 0 || j >= 0) {
        // 从 num1 获取当前位
        int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
        // 从 num2 获取当前位
        int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
        // 当前位的和
        int sum = n1 + n2 + carry;
        // 取个位数加入结果
        result.append(sum % 10);
        // 更新进位
        carry = sum / 10;
        i--;
        j--;
    }
    // 如果最后还有进位，追加到结果中
    if (carry > 0) {
        result.append(carry);
    }
    // 翻转结果字符串并返回
    return result.reverse().toString();
}