039 · Intersection of Two Arrays
My First Thoughts
这道题要找两个 list 的交集，也就是 nums1 和 nums2 里共同出现过的数字。
第一反应是，这题其实是在考察 intersection 这种操作的底层实现。两个数组放在这里，直接能想到的粗暴解法就是：遍历一个数组，看每个数字在不在另一个数组里。
一开始可能会写成这样：
share = []
for num in nums2:
if num in nums1:
share.append(num)
return list(set(share))这个方向是自然的：如果 num 同时出现在 nums2 和 nums1 里，那它就是交集的一部分。
这里最后用：
list(set(share))也能处理重复数字。因为 share 里可能会收集到多个相同的数字，先转成 set 可以去重，再转回 list 符合题目要求的返回类型。
但这个写法还有一个更重要的问题：查找成本。这里每次写：
num in nums1如果 nums1 是 list，Python 可能要从头扫到尾才能确认这个数字在不在里面。数组一长，这个负担就不小。
所以一个很自然的优化是：先把数组变成 set。
nums1_set = set(nums1)
nums2_set = set(nums2)这样做有两个好处：
- set 本身会去重，正好符合“答案里每个数字只能出现一次”
- set 里的查找通常更快，适合反复判断某个数字是否存在
然后再循环一个 set，看它的数字是否也在另一个 set 里。这应该就是正解方向了。
边界上也可以想一下空 list。如果两个都是空，或者一个空一个有，答案肯定是空。循环本身其实能处理这种情况。如果想提前返回，也可以写：
if len(nums1) == 0 or len(nums2) == 0:
return []注意 Python 里不是 nums1.length，而是 len(nums1)。不过这道题原始约束里两个数组长度都至少是 1，所以这个判断不是必须的。
Why That Is Not Enough
这道题主要考察：list 和 set 在查找效率上的差别。
如果用最开始的 list 写法：
share = []
for num in nums2:
if num in nums1:
share.append(num)
return list(set(share))最后的 set(share) 已经能完成去重。真正值得关注的是这一句：
num in nums1当 nums1 是 list 时，in 通常要从左到右找。最坏情况下，要把整个 nums1 扫一遍才能知道当前数字在不在里面。
而这个查找发生在循环里面：
for num in nums2:
if num in nums1:
...也就是说，nums2 里的每个数字，都可能触发一次对 nums1 的线性查找。这就是 list 写法的主要成本。
这题想考察的转折点就是：如果后面会反复问“某个数字是否存在”，可以先把被查询的一边变成 set。
set 更适合做 membership check：
num in nums1：在 list 里查找，可能要逐个比较num in nums1_set：在 set 里查找，平均更快
结果也可以继续用 set 保存，这样去重不必等到最后统一处理，而是在加入答案时自然完成。
Final Idea
从原来的想法出发：
for num in nums2:
if num in nums1:
share.append(num)核心逻辑不用变，还是“遍历一个数组，检查数字是否出现在另一个数组里”。
要改的是两个容器：
- 把
nums1先转成nums1_set，让num in nums1_set查得更快 - 把
share改成 set，这样同一个数字加多次也只会保留一份
也就是：
nums1_set = set(nums1)
share = set()然后遍历 nums2：
for num in nums2:
if num in nums1_set:
share.add(num)最后题目要求返回数组，所以把 set 转回 list：
return list(share)结果顺序不重要，所以 set 转成 list 后顺序不固定也没关系。
Why It Works
nums1_set 保存了 nums1 中出现过的所有不同数字。
遍历 nums2 时，对于每个 num：
- 如果
num in nums1_set，说明它既出现在nums2，也出现在nums1，所以它属于交集 - 如果不在，说明它不是两个数组共同拥有的数字，跳过
结果用 share 这个 set 来保存。set 的特点是同一个值只能出现一次，所以即使 nums2 里有多个相同的数字，最后答案里也只会保留一份。
因此这个过程既找到了两个数组共有的数字，也满足了题目“每个数字只能出现一次”的要求。
Code
def intersection(nums1, nums2):
nums1_set = set(nums1)
share = set()
for num in nums2:
if num in nums1_set:
share.add(num)
return list(share)如果想写得更短，Python 也可以直接使用 set 的交集操作：
def intersection(nums1, nums2):
return list(set(nums1) & set(nums2))第一种写法更适合练习这道题的核心过程：先把 list 变成 set，再用 membership check 判断是否共同出现。
Complexity
| Time | \(O(n + m)\) - n 是 nums1 的长度，m 是 nums2 的长度；先遍历 nums1 建 set，再遍历 nums2 查找 |
| Space | \(O(n + k)\) - nums1_set 最多保存 nums1 中的不同数字，share 保存交集中的不同数字 |
Takeaway
当题目反复问“这个元素在不在另一个集合里”时，要警觉 list 查找可能会反复扫描。把 list 转成 set，通常能把“查找是否存在”这件事表达得更直接，也更高效；如果答案还要求去重，set 也正好能顺手解决重复问题。
← Quiz