👉 数组应用

求和问题

• 15. 三数之和 (opens new window)（双指针法）

交集、差集

• 350. 两个数组的交集 II (opens new window)（利用 map）

数组形式的整数加法

难点：边界进位和进位

• 989. 数组形式的整数加法 (opens new window)

• 66. 加一 (opens new window)

• 415. 字符串相加 (opens new window)（大数相加）

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

var addStrings = function(num1, num2) {
    const len1 = num1.length;
    const len2 = num2.length;

    if (!len1 && !len2) {
        return 0;
    }

    let i = len1 - 1;
    let j = len2 - 1;

    let carry = 0;
    let result = "";
    while (i >= 0 || j >= 0) {
        let number1 = i >= 0 ? +num1[i] : 0;
        let number2 = j >= 0 ? +num2[j] : 0;
        let sum = number1 + number2 + carry;
        result = (sum % 10) + result;
        carry = Math.floor(sum / 10);

        i--;
        j--;
    }

    if (carry) {
        result = carry + result;
    }

    return result;
};

• 43. 字符串相乘 (opens new window)（大数相乘）

var multiply = function(num1, num2) {
    const len1 = num1.length;
    const len2 = num2.length;

    if (!len1 && !len2) return 0;
    if ((len1 === 1 && num1[0] === 0) || (len2 === 1 && num2[0] === 0))
        return 0;

    // 一个n位数和一个m位数相乘，最多会有n+m位数
    let result = new Array(len1 + len2).fill(0);

    for (let i = len1 - 1; i >= 0; i--) {
        // 字符串类型转换成数字类型
        let n1 = +num1[i];

        for (let j = len2 - 1; j >= 0; j--) {
            const multi = n1 * num2[j] + result[i + j + 1];
            // 当前位
            result[i + j + 1] = multi % 10;

            // 向前进位
            result[i + j] = Math.floor(multi / 10) + result[i + j];
        }
    }

    while (result[0] === 0) {
        result.shift();
    }

    return result.length ? result.join("") : "0";
};