LeetCode 349. 两个数组的交集
题目描述
题意分析
返回同时出现在两个数组中的所有不同数值，每个公共值只能输出一次，出现次数不影响答案。结果顺序不限；若没有公共值，则返回空数组。
两个数组都不保证有序，所以不能直接根据当前位置的大小决定跳过哪些元素。题目要的是集合交集，不需要统计重复次数，也不需要修改输入数组。
解法：哈希集合，命中后删除
核心思路
[!blue]
用哈希集合记录一个数组中的不同值，便能在扫描另一个数组时快速判断当前值是否在两边都出现。把集合建在较短数组上，可以让保存的候选数量更少，扫描次数不变。
为避免重复输出，将集合的含义进一步限定为“来自第一个数组、但尚未加入答案的值”。扫描第二个数组时，当前值在集合中就加入答案，并立刻从集合删除；以后再遇到同值便无法再次命中。
这保证每个输出值一定同时来自两个数组，且最多输出一次。反过来，任意公共值第一次在第二个数组中出现时，必然还在候选集合中，因而一定会被记录，所以结果也不会遗漏。
Java 用
remove的布尔返回值同时完成查询和删除，Go 先查询存在性再删除。Java 结果数组按候选总量预分配，但实际交集可能更小，所以用size记录有效长度，最后只返回有效前缀。
解题步骤
- 若
nums1更长，交换两个局部数组引用，让nums1成为较短的一侧；数组内容不变。- 将
nums1的元素加入候选集合，自动合并重复值。- 扫描
nums2，仅当当前值仍在集合中时记录答案，并立即删除该候选。- Java 截取结果缓冲区的有效前缀；Go 返回已经追加的切片，均无需排序。
代码实现
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
Set<Integer> candidates = new HashSet<>();
for (int num : nums1) {
candidates.add(num);
}
int[] answer = new int[candidates.size()];
int size = 0;
for (int num : nums2) {
// 命中后立刻删除候选，同一值只会输出一次。
if (candidates.remove(num)) {
answer[size++] = num;
}
}
return Arrays.copyOf(answer, size);
}
}
func intersection(nums1 []int, nums2 []int) []int {
if len(nums1) > len(nums2) {
nums1, nums2 = nums2, nums1
}
candidates := make(map[int]struct{}, len(nums1))
for _, num := range nums1 {
candidates[num] = struct{}{}
}
answer := make([]int, 0, len(candidates))
for _, num := range nums2 {
if _, ok := candidates[num]; ok {
answer = append(answer, num)
// 命中后立刻删除候选，同一值只会输出一次。
delete(candidates, num)
}
}
return answer
}
复杂度分析
- 时间复杂度：平均 $O(m+n)$。建立集合与扫描数组各一遍，哈希集合的插入、查询和删除平均为 $O(1)$。
- 空间复杂度：$O(\min(m,n))$。集合建在较短数组上，答案长度也不会超过较短数组的不同元素个数。
关键点总结
[!green]
- 先确认题目要「去重后的交集」，若要保留重复次数，应改用计数哈希表。
- 集合建在较短数组上，时间不变，但额外空间更稳。
remove同时完成「是否存在」和「防止重复输出」两个动作，这是本解法的关键。- 正确性依赖的核心不变量是：答案保存已扫描部分的交集，集合保存尚未输出的候选值。
易错点总结
[!yellow]
- 只判断存在却不删除，也不另外去重，会让第二个数组中的重复值多次进入答案。
- 扫描第二个数组时不能将未命中的值加入候选集合，否则之后的同值可能被误认为公共值。
- Java 必须返回有效前缀，不能把预分配数组中未使用的默认零一起返回。
- 未排序的输入不具备单调性，不能直接用双指针的大小比较排除候选。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 350. 两个数组的交集 II | 简单 | 原题交集保留重复次数，本题每个公共值只输出一次，集合即可。 |
| 2215. 找出两数组的不同 | 简单 | 同样按集合处理重复值，原题分别输出两个方向的差集，本题输出公共部分。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！