C++代码随想录刷题知识分享-----数组交集—LeetCode 349

1 · 题目描述

给定两个整型数组 nums1 和 nums2，请返回它们的交集。

• 交集中 每个元素必须是唯一的。
• 输出结果的顺序可以任意。

示例	输入	输出	说明
1	nums1 = [1,2,2,1], nums2 = [2,2]	[2]	2 只出现一次
2	nums1 = [4,9,5], nums2 = [9,4,9,8,4]	[4,9] 或 [9,4]	顺序不作要求

限制

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

---

2 · 解题思路

核心：用哈希表（集合）做“存在性”判定。

1. 去重 + 查询快速 —— unordered_set 的查找、插入都是 O(1)O(1)O(1)。
2. 把 nums1 放进集合 set1。
3. 遍历 nums2，若 set1 中存在该元素，就放进结果集合 resSet（自动唯一）。
4. 最后把 resSet 转成 vector 返回。

与双重循环相比，时间复杂度从 O(n2)O(n^2)O(n2) 降为 O(n)O(n)O(n)。

---

3 · C++ 代码

3.1 暴力法

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> res;for (int x:nums1){for (int y:nums2){if( x==y ){res.push_back(x);}}}% 去重＋排序set<int> s(res.begin(), res.end());% 放在新容器当中vector<int> res1(s.begin(), s.end());return res1;}
};

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> set1(nums1.begin(), nums1.end());unordered_set<int> set2(nums2.begin(), nums2.end());vector<int> res;for (int x1 : set1){for (int x2 : set2){if (x1==x2){res.push_back(x1);}}}return res;}};

3.2 使用map的暴力法

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> hash1;unordered_map<int, int> hash2;vector<int> res;for (int i:nums1){hash1[i]++;}for (int i:nums2){hash2[i]++;}for (auto& [key1, val1] : hash1) {for (auto& [key2,val2]:hash2){if (key1==key2 && val1>0 && val2>0){res.push_back(key1);}                    }}return res;}
};

3.3 最合适的方法

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// ① 用 unordered_set 存储 nums1 中的所有元素unordered_set<int> set1(nums1.begin(), nums1.end());// ② 结果集合，自动去重unordered_set<int> resSet;// ③ 遍历 nums2，判断是否在 set1 中for (int x : nums2) {if (set1.count(x)) {   // 存在于 set1resSet.insert(x);  // 放入结果集合（去重）}}// ④ 将结果集合转成 vectorreturn vector<int>(resSet.begin(), resSet.end());}
};

4 · 复杂度分析

指标	复杂度	说明
时间	O(m+n)O(m + n)O(m+n)	m = nums1.size(), n = nums2.size()
空间	O(m)O(m)O(m)	set1 最多 m 个元素，resSet ≤ m

---

5 · 其他可行解法

方法	思路	复杂度	适用场景
排序 + 双指针	排序后用双指针扫描去重	O(nlog⁡n+mlog⁡m)O(n\log n+m\log m)O(nlogn+mlogm)	两数组已排好序或内存受限
set 直接构造	set<int> s(nums1) + 遍历 nums2	O(nlog⁡n)O(n\log n)O(nlogn)	结果需要有序
布尔桶	数值范围已知 [0,1000][0,1000][0,1000]，用 bool 数组标记	O(n+m)O(n+m)O(n+m) 空间 O(1001)O(1001)O(1001)	值域小且固定

---

6 · 常见错误 / 易混点

误区	为什么错
使用双 for 嵌套	O(n2)O(n^2)O(n2) 超时风险
存两张 map 再双循环	多余且还是 O(n2)O(n^2)O(n2)
返回 set<int>	LeetCode 要求 vector<int> 返回值类型不匹配
没去重直接 push_back	交集须唯一，必须用 set 或额外判断

---

7 · 进阶与扩展

1. 交集保留重复 → LeetCode 350，需要用 unordered_map<int,int> 统计每个数出现频次。
2. 三个或更多数组的交集 → 先对最短那两个取交，再与第三个取交，重复直至完成。
3. 流式数据实时求交集 → 可用 Bloom Filter 或位图等概率 & 空间优化算法。

---

8 · 总结

用 unordered_set 能在 O(n)O(n)O(n) 时间、O(n)O(n)O(n) 空间内完成“唯一交集”——既快又简洁，是此题公认最优解。掌握哈希集合思想，在很多去重 + 判断存在性的题目中都能举一反三。