0349.两个数组的交集

难度：🟢 简单

标签：数组、哈希表、双指针、排序

链接：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] 也是可通过的

解题思路

核心思想

本题的核心是找出两个数组中共有的元素，并确保返回的结果中没有重复项。解决这个问题的关键在于如何高效地存储和查找一个数组中的元素，以判断它是否存在于另一个数组中。

思路选择

哈希集合（Set）法 是解决此问题的最优思路。Set 是一种特殊的数据结构，它只存储唯一的值，并能提供近乎 O(1) 时间复杂度的添加和查找操作。

• 我们可以先将一个数组（例如 nums1）的所有元素存入一个 Set，这会自动处理掉 nums1 内部的重复元素。

• 然后，遍历第二个数组（nums2），对于 nums2 中的每一个元素，我们去 Set 中检查它是否存在。

• 如果存在，说明这个元素是交集的一部分，我们将其加入到另一个用于存放结果的 Set 中，以保证最终结果的唯一性。

关键步骤

1. 初始化：创建一个哈希集合 set1，并将 nums1 的所有元素存入其中。再创建一个用于存放结果的空哈希集合 resultSet。

2. 循环遍历：遍历第二个数组 nums2。

3. 查找与添加：对于 nums2 中的每一个元素 num，检查它是否存在于 set1 中。 a. 如果 set1.has(num) 为 true，则将 num 添加到 resultSet 中。

4. 返回结果：遍历结束后，将 resultSet 转换为数组并返回。

代码实现 (推荐)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
    const set1 = new Set(nums1);
    const resultSet = new Set();

    for (const num of nums2) {
        // 如果 set1 中存在 num，则其为交集元素
        if (set1.has(num)) {
            // 添加到结果 set 中，自动处理重复
            resultSet.add(num);
        }
    }

    // 将结果 set 转换为数组
    return Array.from(resultSet);
};

复杂度分析

• 时间复杂度：O(m + n) 其中 m 和 n 分别是两个数组的长度。构建 Set 需要 O(m) 的时间，遍历 nums2 需要 O(n) 的时间。

• 空间复杂度：O(m) 或 O(n) 我们需要一个哈希集合来存储其中一个数组的元素。为了优化空间，可以优先选择将较短的数组存入集合。

相关题目

• 0350.两个数组的交集 II

• 0217.存在重复元素

总结

本题是考察哈希数据结构应用的入门题。通过使用 Set，可以高效地解决去重和查找的问题，这是处理数组交集、并集、差集等问题的通用且高效的方法。