LeetCode 350. 两个数组的交集 II
题目描述
题意分析
返回两个数组的公共元素，并保留能在两边一一配对的重复次数。某个值在两侧分别出现多少次，答案中就取这两个次数的较小值；结果顺序不限，不必连续选取，也不需要修改输入数组。
本题与只返回不同公共值的交集不同，不能用集合直接去重。题面还追问输入已有序、两侧长度差距很大，以及较大数组保存在磁盘上的情况，分别需要考虑计数空间和顺序读取。
解法：哈希表统计较短数组频率
核心思路
[!blue]
用频次表记录一个数组中每个值还可以匹配多少次，再逐项扫描另一个数组。将较短数组用于建表，可以减少保存的元素数量；交换两侧不会改变每个值能够配对的总次数。
freq[value]不是已经匹配的数量，而是较短数组里尚未被消耗的出现次数。扫描到另一侧的value时，只有额度大于零才输出一次，并立即减一，表示两边各消耗了一个同值元素。对任意值，匹配次数不可能超过较短侧的总额度，也不可能超过另一侧实际遇到的次数；只要两边还都有剩余就会继续配对，因此最后恰好达到两侧次数的最小值，既不重复使用元素，也不会遗漏可匹配项。
Java 为结果分配较短数组长度的缓冲区，
size记录实际输出长度，最后只复制有效前缀；Go 按匹配成功次数追加。频次降为零后，即使键仍存在，也不能再输出。
解题步骤
- 若
nums1更长，交换参数后处理，使计数表始终建立在较短一侧；最多交换一次。- 遍历较短数组，统计每个值的出现次数。
- 扫描另一数组，当前值的剩余次数大于零时写入答案，并立即将对应次数减一。
- 返回实际写入的结果，Java 只保留缓冲区有效前缀。
代码实现
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
// 让较短数组承担计数存储，交换不改变交集的配对结果。
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums1) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int[] result = new int[nums1.length];
int size = 0;
for (int num : nums2) {
int count = freq.getOrDefault(num, 0);
// 只有剩余额度才配对，输出后立即消费一次，保留正确重复次数。
if (count > 0) {
result[size++] = num;
freq.put(num, count - 1);
}
}
// 仅返回实际写入的有效前缀，未使用的默认值不属于交集。
return Arrays.copyOf(result, size);
}
}
func intersect(nums1, nums2 []int) []int {
// 让较短数组承担计数存储，交换不改变交集的配对结果。
if len(nums1) > len(nums2) {
return intersect(nums2, nums1)
}
freq := make(map[int]int, len(nums1))
for _, num := range nums1 {
freq[num]++
}
result := make([]int, 0, len(nums1))
for _, num := range nums2 {
// 只有剩余额度才配对，输出后立即消费一次，保留正确重复次数。
if freq[num] > 0 {
result = append(result, num)
freq[num]--
}
}
return result
}
复杂度分析
- 时间复杂度：期望 $O(m+n)$；哈希表单次读写的期望代价为 $O(1)$。
- 空间复杂度：$O(\min(m,n))$，计数表建立在较短数组上；不计返回结果。
关键点总结
[!green]
- 本题是多重集合交集，重复次数取两侧频率的较小值。
- 计数值是会被消耗的额度，匹配后必须立即减 1。
- 算法对输入对称时，让较短的一侧承担额外空间。
进阶：有序数组与受限内存
核心思路
[!blue]
若两个数组已经升序排列，可以用双指针直接配对，不再建立频次表。
i、j分别指向两边尚未处理的最小元素：相等就输出一次并同时前进，相当于各消费一次出现，重复值自然逐个配对。若
nums1[i] < nums2[j]，第二个数组后面所有值都不小于nums2[j]，当前较小值已经找不到匹配，可以安全跳过i；另一侧较小时同理跳过j。任一数组耗尽，剩余元素都无法再配对，立即结束。下面的
intersectSorted明确以两个输入均已升序为前提。若输入无序，也可先排序后调用，但需要另计排序时间，且原地排序会改变输入；无序时保留上面的短数组计数解法即可。
解题步骤
- 初始化两个指针为零，准备结果缓冲区。
- 两边都还有元素时，比较当前值；较小的一侧前进一步。
- 值相等时输出一次，并同时前进两个指针，不跳过后续相同值。
- 任一侧结束后，返回已记录的交集。
代码实现
class Solution {
public int[] intersectSorted(int[] nums1, int[] nums2) {
int[] result = new int[Math.min(nums1.length, nums2.length)];
int i = 0;
int j = 0;
int size = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
result[size++] = nums1[i];
i++;
j++;
}
}
return Arrays.copyOf(result, size);
}
}
func intersectSorted(nums1, nums2 []int) []int {
result := make([]int, 0)
i, j := 0, 0
for i < len(nums1) && j < len(nums2) {
if nums1[i] < nums2[j] {
i++
} else if nums1[i] > nums2[j] {
j++
} else {
result = append(result, nums1[i])
i++
j++
}
}
return result
}
复杂度分析
- 时间复杂度：$O(m + n)$，两个指针都只向前，每次至少前进一个。
- 空间复杂度：双指针本身为 $O(1)$；结果及其构造缓冲区最多占 $O(\min(m,n))$，Java 最后还会复制有效前缀。
关键点总结
[!green]
- 两侧已排序时，单调性允许跳过较小值，相等值逐次配对保留正确重复次数。
- 两侧长度差距很大且无序时，仍优先给短数组建频次表，只顺序扫描长数组，空间随短数组增长。
- 若短数组可放入内存、长数组在磁盘上，频次表只建立一次，长数组分块顺序读取，每次匹配都持续扣减同一张表，不在块之间重置额度。结果也可以顺序输出，无需保存整个长数组。
- 若两侧在磁盘上且已经有序，可以各保留一个读取缓冲区，沿用双指针归并；若两侧都无序且无法装入内存，则需先做外部排序再归并，不能假设整条长数组可以常驻内存。
易错点总结
[!yellow]
- 使用集合会丢掉重复次数，不能表示本题要求的一一配对结果。
- 匹配后不减少额度，或只检查键存在却不检查次数，会重复使用同一个输入元素。
- 有序双指针只适用于已经排序的输入，未经排序时大小关系不能指导跳过元素。
- 有序配对成功后两指针都要前进，否则可能重复消费同一个位置。
- 分块读取较大数组时不能为每个块重建或重置短数组的频次，否则各块会重复使用相同额度。
- Java 返回整个预分配缓冲区，会把尚未使用的默认零混入答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 349. 两个数组的交集 | 简单 | 本题交集数量由两边频次的最小值决定，原题只关心是否共同出现。 |
| 299. 猜数字游戏 | 中等 | 忽略位置的匹配总数同样是多重集合交集，原题再扣除精确位置匹配。 |