【LeetCode】349. 两个数组的交集（简单）——代码随想录算法训练营Day06

题目链接：349. 两个数组的交集

题目描述

给定两个数组?nums1?和?nums2?，返回?它们的交集?。输出结果中的每个元素一定是?唯一?的。我们可以?不考虑输出结果的顺序?。

示例 1：

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

输出：[2]

示例 2：

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

输出：[9,4]

解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

文章讲解：代码随想录

视频讲解：学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集_哔哩哔哩_bilibili

题解1：Set 用作哈希表

思路：题目给出两个数字 nums1 和 nums2，要求它们的交集，即找出?nums2 中的元素同时也在 num1 中元素，就可以考虑使用哈希表来求解。由于结果要求去重，因此使用 Set 作为哈希表。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const res = new Set(); // 存放结果
    const nums1Set = new Set(nums1); // 将 nums1 转换为 set
    nums2.forEach(num => nums1Set.has(num) && res.add(num)); // 将存在于 nums1Set 中的 nums2 中的元素加入到结果 set 中
    return [...res];
};

分析：分别遍历了一次?nums1 和 nums2，额外构建的 Set 规模和 nums1、nums2 有关，时间复杂度为 O(n)，空间复杂度为 O(n)。

题解2：Array 用作哈希表

思路：题目中给的数组元素范围为0到1000，数字不是很大，因此可以考虑构建一个长度为1001的

数组来解决此题。由于数组直接根据下标索引，而 Set 在插入删除元素时还需要做哈希映射，把数组用作哈希表运行速度会更快。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const res = new Set();
    const nums1Arr = new Array(1001); // 题目中给出的数组元素范围为0~1000
    nums1.forEach(num => nums1Arr[num] = true);
    nums2.forEach(num => nums1Arr[num] && res.add(num));
    return [...res];
};

分析：时间复杂度为 O(n)，空间复杂度为 O(n)。

题解3：Map 用作哈希表

思路：我们也可以把 Map 用作哈希表，将 nums1 中的元素作为哈希表的键，记录 nums1 中出现过的元素。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const res = new Set();
    const nums1Map = new Map(); // Map 用作哈希表
    nums1.forEach(num => nums1Map.set(num, true));
    nums2.forEach(num => nums1Map.has(num) && res.add(num));
    return [...res];
};

分析：时间复杂度为 O(n)，空间复杂度为 O(n)。

收获

在使用哈希表解题时，明确什么时候用数组，什么时候用 Map，什么时候用 Set 是非常重要的。

• 当题目给出的数据的结构是可数的（如字符串中的 ASCII 字符，固定范围内的数字等），就可以考虑把数组用作哈希表来解决问题。如果题目中的数字范围很大，把数组用作哈希表就不合适了。
• 当题目给出的数据为数字且需要做去重操作时，就可以考虑把 Set 用作哈希表。
• 其余情况把 Map 用作哈希表。