LeetCode 349简单哈希表
两个数组的交集 图解题解
这道题到底在问什么
给定两个数组 nums1 和 nums2，返回它们的交集。结果里每个元素只出现一次，顺序不限。
- 输入
- nums1 = [4,9,5,9,4]，nums2 = [9,4,9,8,4,7]
- 输出
- [9,4]（两边都有的数字，去重）
最优解：一步一步想明白
- 3思路一句话：先把 nums1 装进集合 seen（自动去重），再扫 nums2，在 seen 里的就是交集、收进 ans（也去重）。下面一步步演给你看。
- 4第一步：把 nums1 的数字全倒进集合 seen，重复的自动去掉，得到 {4, 9, 5}。接下来开始扫 nums2。
- 5指针 i 走到下标 0，这一格的值是 9。去集合 seen 里查它在不在。
- 69 在集合里、之前还没收过，是新的交集元素，收进 ans。集合侧栏里它被点亮了。
- 7指针 i 走到下标 1，这一格的值是 4。去集合 seen 里查它在不在。
- 84 在集合里、之前还没收过，是新的交集元素，收进 ans。集合侧栏里它被点亮了。
- 9指针 i 走到下标 2，这一格的值是 9。去集合 seen 里查它在不在。
- 109 确实在集合里，可 ans 里已经记过一次了。交集每个数只算一次，所以这次不再收，ans 保持不变。
- 11指针 i 走到下标 3，这一格的值是 8。去集合 seen 里查它在不在。
- 128 不在集合 seen 里，说明 nums1 根本没出现过这个数，不是交集，标红跳过。
- 13指针 i 走到下标 4，这一格的值是 4。去集合 seen 里查它在不在。
- 144 确实在集合里，可 ans 里已经记过一次了。交集每个数只算一次，所以这次不再收，ans 保持不变。
- 15指针 i 走到下标 5，这一格的值是 7。去集合 seen 里查它在不在。
- 167 不在集合 seen 里，说明 nums1 根本没出现过这个数，不是交集，标红跳过。
- 17指针 i 走到下标 6，这一格的值是 5。去集合 seen 里查它在不在。
- 185 在集合里、之前还没收过，是新的交集元素，收进 ans。集合侧栏里它被点亮了。
- 19指针 i 走到下标 7，这一格的值是 6。去集合 seen 里查它在不在。
- 206 不在集合 seen 里，说明 nums1 根本没出现过这个数，不是交集，标红跳过。
- 21指针 i 走到下标 8，这一格的值是 5。去集合 seen 里查它在不在。
- 225 确实在集合里，可 ans 里已经记过一次了。交集每个数只算一次，所以这次不再收，ans 保持不变。
- 23指针 i 走到下标 9，这一格的值是 9。去集合 seen 里查它在不在。
- 249 确实在集合里，可 ans 里已经记过一次了。交集每个数只算一次，所以这次不再收，ans 保持不变。
- 25扫到末尾，nums2 里凡是在集合中的格子都被点亮，去重后的交集就是 [9, 4, 5]。
⚠️ 容易写错的地方
✗ 错：用两层循环逐对比较
✓ 对：先建集合，再一遍扫描判断在不在
两层循环是 O(n×m)，数据一大就超时；集合查询 O(1) 把它降到 O(n+m)
✗ 错：结果里出现重复数字
✓ 对：答案也用集合 ans 收集
nums2 里同一个数可能出现多次，不去重会让交集里冒出重复元素
✗ 错：把 nums2 也整个装进集合再求交
✓ 对：只需把 nums1 装集合，nums2 边扫边查
多建一个集合没必要，边扫边查更省，逻辑也更直白
完整代码（Python / C++ / Java）
Python
def intersection(nums1, nums2):
seen = set(nums1) # nums1 装进集合，自动去重
ans = set() # 交集结果，也用集合防重复
for x in nums2: # 扫 nums2 的每个数
if x in seen: # 在集合里 → 两边都有
ans.add(x) # 收进交集（重复自动忽略）
return list(ans)C++
vector<int> intersection(vector<int>& nums1, vector<int>& nums2){
unordered_set<int> seen(nums1.begin(), nums1.end());
unordered_set<int> ans;
for (int x : nums2)
if (seen.count(x)) ans.insert(x);
return vector<int>(ans.begin(), ans.end());
}Java
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> seen = new HashSet<>();
for (int x : nums1) seen.add(x);
Set<Integer> ans = new HashSet<>();
for (int x : nums2) if (seen.contains(x)) ans.add(x);
int[] r = new int[ans.size()]; int i = 0;
for (int x : ans) r[i++] = x;
return r;
}复杂度
时间
O(n + m)
建 seen 扫一遍 nums1（n 个），再扫一遍 nums2（m 个），集合查询是 O(1)
空间
O(n)
集合 seen 最多装下 nums1 去重后的全部数字
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两个数组的交集 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用集合而不是两层循环？+
两层循环逐对比较是 O(n×m)，数据大就超时。集合把「某个数在不在 nums1 里」变成 O(1) 查询，整体降到 O(n+m)。
如果要保留出现次数（求交集的多重集），怎么改？+
那就不能用集合，要用计数哈希表（Counter）记每个数在两边各出现几次，交集里该数的次数取两边的较小值。
结果需要排序吗？+
本题不要求顺序。如果面试官要求有序，最后对结果排个序即可，多花 O(klogk)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 两个数组的交集 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。