取交集

给定两个数组，写一个方法来计算它们的交集。
例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]

一、初步解答

function getIntersection (num1, num2) {
    var result = [];
    num1.forEach(num => {
        if (num2.indexOf(num) !== -1) {
            result.push(num);
        }
    });
    return result;
}

// 简化版
function getIntersection (num1, num2) {
    return num1.filter(num => {
        return num2.includes(num);
    });
}

二、易错点

举个反例： num1 = [1, 1]; num2 = [1];

对于这种情况，要么利用空间换取时间，要么提高时间复杂度

• 空间换时间：

function getIntersection (num1, num2) {
    const maps = {};
    const result = [];
    num1.forEach(num => {
        if (maps[num]) {
            maps[num] += 1;
        } else {
            maps[num] = 1;
        }
    });

    num2.forEach(num => {
        if (maps[num]) {
            result.push(num);
            maps[num] -= 1;
        }
    });
    return result;
}

• 不使用额外空间：

function getIntersection (num1, num2) {
    return num1.filter(num => {
        let index = num2.indexOf(num);

        if (index !== -1) {
            num2.splice(index, 1);
            return true;
        }
        return false;
    });
}

三、相关讨论：

• https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/102