349. 两个数组的交集

🟢   🔖  数组 哈希表 双指针 二分查找 排序  🔗 力扣 LeetCode

题目

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [9,4]

Explanation: [4,9] is also accepted.

Constraints:

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

题目大意

给定两个数组 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） 数据结构，它具有自动去重和高效查找的特性。

1. 将 nums1 和 nums2 分别转换为集合 set1 和 set2，从而去除数组中的重复元素，并提高查找效率。
2. 使用 filter 方法遍历 set1 中的元素，检查每个元素是否同时存在于 set2 中。如果存在，则将该元素加入到最终结果中。最后，返回交集结果。
3. 也可以使用 ES6 的 Set 交集操作符 .intersection()，可以进一步简化代码。

复杂度分析

• 时间复杂度：O(n + m)，其中 n 和 m 是两个数组的长度。
  • 构建 set1 和 set2 的时间复杂度为 O(n + m)。
  • filter 方法遍历 set1 的时间复杂度是 O(n)。
  • 总的时间复杂度为 O(n + m)
• 空间复杂度：O(n + m)，需要分别存储两个集合 set1 和 set2。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
	const set1 = new Set(nums1); // 去重并存储 nums1 中的元素
	const set2 = new Set(nums2); // 去重并存储 nums2 中的元素

	// 过滤出 set1 中存在于 set2 的元素
	return [...set1].filter((num) => set2.has(num));
	// 或者使用原生方法
	return [...set1.intersection(set2)];
};

相关题目

题号	标题	题解	标签	难度	力扣
350	两个数组的交集 II	[✓]	数组 哈希表 双指针 2+	🟢	🀄️ 🔗
1213	三个有序数组的交集 🔒		数组 哈希表 二分查找 1+	🟢	🀄️ 🔗
2085	统计出现过一次的公共字符串	[✓]	数组 哈希表 字符串 1+	🟢	🀄️ 🔗
2143	在两个数组的区间中选取数字 🔒		数组 动态规划	🔴	🀄️ 🔗
2215	找出两数组的不同	[✓]	数组 哈希表	🟢	🀄️ 🔗
2248	多个数组求交集		数组 哈希表 计数 1+	🟢	🀄️ 🔗
2540	最小公共值		数组 哈希表 双指针 1+	🟢	🀄️ 🔗
3002	移除后集合的最多元素数		贪心 数组 哈希表	🟠	🀄️ 🔗