LeetCode 349简单哈希表
两个数组的交集 图解题解
这道题到底在问什么
给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的，可以不考虑输出结果的顺序。
- 输入
- nums1 = [1,2,2,1], nums2 = [2,2]
- 输出
- [2]
- 输入
- nums1 = [4,9,5], nums2 = [9,4,9,8,4]
- 输出
- [9,4]
- 解释
- [4,9] 也可以通过，因为结果顺序不要求。
先想最直接的笨办法
暴力法的麻烦点正是“查找慢”和“去重麻烦”。集合一次解决这两个问题。（动画第 3 步）
最优解：一步一步想明白
- 3暴力法的麻烦点正是“查找慢”和“去重麻烦”。集合一次解决这两个问题。
- 4不变量：s1 保存 nums1 出现过的唯一值；ans 保存已经确认属于交集的唯一值。
- 5s1 = set(); ans = set()动画上半段处理 nums1 的输入，建立 s1；下半段处理 nums2 的输入，查 s1 并更新 ans。
- 6s1.add(1)集合里还没有 1，把 1 加进去。之后查 1 是否出现过就是 O(1) 平均时间。
- 7s1.add(2)2 也加入 s1。到这里，nums1 里出现过的候选交集值已经有 1 和 2。
- 8s1.add(2) # set 自动去重这就是集合的第一层去重：nums1 里有两个 2，但 s1 里只保留一个 2。
- 9s1.add(1) # set 自动去重nums1 扫完后，s1={1,2}。接下来扫描 nums2，只需要判断每个 x 是否在 s1 里。
- 10for x in nums2: x = 2; if x in s1: ans.add(x)nums2 的第一个 2 在 s1 里，说明两个数组都出现过 2，把它加入结果集合 ans。
- 11for x in nums2: x = 2; if x in s1: ans.add(x)nums2 里也有两个 2，但 ans 是集合，所以第二次 add(2) 不会产生重复答案。
- 12return list(ans)最终 ans 只有一个元素 2。题目不要求顺序，所以把集合转成列表返回即可。
- 15这题的可迁移点是：先用一个集合保存“出现过”，再用另一个集合保存“确认命中且不重复”。
⚠️ 容易写错的地方
✗ 错：用列表收集结果，x 在 s1 中就 append 一次
✓ 对：用 ans=set() 收集结果
nums2 里可能重复出现同一个交集元素，结果必须唯一。
✗ 错：要求输出顺序固定
✓ 对：顺序不重要，任意顺序都能通过
题目明确可以不考虑输出顺序。
✗ 错：每次都在另一个数组里线性查找
✓ 对：先把 nums1 转成 set 再 O(1) 平均查找
哈希集合能避免重复扫描。
完整代码（Python）
Python
class Solution:
def intersection(self, nums1, nums2):
s1 = set(nums1)
ans = set()
for x in nums2:
if x in s1:
ans.add(x)
return list(ans)复杂度
时间复杂度
O(m+n)
m=len(nums1), n=len(nums2)。建 s1 扫 nums1，查交集扫 nums2。
空间复杂度
O(m+n)
s1 和 ans 最多保存两个数组中的不同元素。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两个数组的交集 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「哈希表」，换最直接的暴力解会差在哪？+
哈希表抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。