题解 | #大数加法#

模拟人工加法的思路

就像我们自己用笔在草稿纸上手动计算加法一样，从后往前加，一位一位地进行计算。

• 用循环遍历长度较长的字符串的同时，也可以遍历长度较短的数，在长度较短的数遍历完后，剩下的应该用0来代替计算。

• 如果当前位置的和sum>10，就说明有进位，用变量将进位保存，carry=1，否则carry=0。

• 在循环结束后，需要考虑第一个位置的加法有没有进位，若有进位，需要在前面拼接字符'1'。

代码实现

function solve( s ,  t ) {
    if (!s || !t) {
        return s || t || '';
    }
    let result = '';
    let carry = 0; // 保存进位
    let small = s; // 字符串长度短的数
    let big = t; // 字符串长度长的数
    
    if (s.length > t.length) {
        small = t;
        big = s;
    }
    // 两个字符串的长度差，主要用来索引长度短的字符串
    const difference = big.length - small.length;
    
    for (let i = big.length - 1; i >= 0; i--) {
        let smallNum = parseInt(small[i-difference]);
        (i - difference < 0) && (smallNum = 0); // 长度短的数不够位的话，用0来代替计算。
        // 保存当前位置的和
        const sum = parseInt(big[i]) + smallNum + carry;

        if (sum > 9) {
            // 和大于9，说明有进位，则当前位置的和为sum-10，并且保存进位数。
            result = (sum - 10) + result;
            carry = 1;
        } else {
            result = sum + result;
            carry = 0;
        }
    }
    // 最后的进位数也要算上
    carry === 1 && (result = '1' + result);
    return result;
}

时间复杂度：O(max(n,m))，n为s.length，m为t.length，即长度较长的字符串决定时间复杂度。

空间复杂度：O(1)