# 349 两个数组的交集

# 题目

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

说明：

输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

# 题解

TIP

执行用时：72 ms, 在所有 JavaScript 提交中击败了 95.71% 的用户
内存消耗：38.7 MB, 在所有 JavaScript 提交中击败了 33.18% 的用户

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let set2 = new Set(nums2)
    let result = new Set()
    nums1.forEach(item => {
        set2.has(item) && result.add(item)
    })
    return [...result]
};

时间复杂度： `O(n^2)`，使用 forEach循环和has方法，n 为 nums1 的长度，
空间复杂度： `O(n)`，使用两个变量来保存值
最好情况：
最坏情况：

通过 while循环一次遍历 nums2 里的每一个元素，其他同上

TIP

执行用时：92 ms, 在所有 JavaScript 提交中击败了 43.4% 的用户
内存消耗：38.8 MB, 在所有 JavaScript 提交中击败了 30.09% 的用户

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let l = nums2.length
    let result = new Set()
    while(l--) {
        nums1.includes(nums2[l]) && result.add(nums2[l])
    }

    return [...result]
};

时间复杂度： `O(n^2)`，使用 while循环和 includes 方法
空间复杂度： `O(n)`，使用一个变量来保存值
最好情况：
最坏情况：

第一次遍历 nums1 里面的元素，把每一项放到 hash 里面，第二次遍历 nums2，把结果存放到 Set 里面。

TIP

执行用时：80 ms, 在所有 JavaScript 提交中击败了 83.39% 的用户
内存消耗：38.7 MB, 在所有 JavaScript 提交中击败了 32.26% 的用户

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let l1 = nums1.length
    let l2 = nums2.length
    let hash = []
    let result = new Set()
    while(l1--) {
        hash[nums1[l1]] = nums1[l1]
    }

    while(l2--) {
        if(hash[nums2[l2]] != undefined) {
            result.add(nums2[l2])
        }
    }

    return [...result]
};

时间复杂度： `O(n)`，分别使用两个 while循环，第二个 while循环里面使用`O(1)`的方法去判断是否存在元素
空间复杂度： `O(n)`，使用两个变量来保存值
最好情况：
最坏情况：

与上面不同的是，第二个 while循环利用了双指针去判断元素是否存在

TIP

执行用时：68 ms, 在所有 JavaScript 提交中击败了 98.28% 的用户
内存消耗：38.4 MB, 在所有 JavaScript 提交中击败了 46.73% 的用户

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let l1 = nums1.length
    let l2 = nums2.length
    let hash = []
    let result = new Set()
    while(l1--) {
        hash[nums1[l1]] = nums1[l1]
    }

    let left = 0, right = l2
    while(left <= right) {
        if(hash[nums2[left]] != undefined) {
            result.add(nums2[left])
        }
        if(hash[nums2[right]] != undefined) {
           result.add(nums2[right]) 
        }
        
        left++
        right--
    }

    return [...result]
};

时间复杂度： `O(n)`，分别使用两个 while循环，第二个 while循环里面使用`O(1)`的方法去判断是否存在元素
空间复杂度： `O(n)`，使用两个变量来保存值
最好情况：
最坏情况：

← 344 反转字符串 383 赎金信 →