LeetCode 350. 两个数组的交集 II

约 5 分钟
文章信息 11 个分类 6 个标签
分类
LeetCode CodeTop 简单 未解决 历史考题 5-10 字节跳动 阿里巴巴 腾讯 虾皮 作业帮
标签
数组 哈希表 排序 双指针 二分查找 双指针经典题
目录

题目描述

✅ 350. 两个数组的交集 II

image-20230311215137144

题意分析

题目要的不是「哪些数字同时出现在两个数组里」，而是「同时出现的数字各自应该出现几次」。nums1 = [1,2,2,1]、nums2 = [2,2] 的答案是 [2,2] 而不是 [2]，说明答案是一个允许重复的结果集，重复次数取两边出现次数的较小值。

输出顺序不作要求，这条约束很关键：它说明我们不需要保持任何一侧的相对顺序，也就不需要排序，可以自由选择「一遍统计、一遍匹配」的处理方式。

两个数组的长度可以差得很悬殊，而额外空间只跟我们选择去统计的那一侧有关，所以「统计哪一侧」是一个可以主动优化的自由度。

边界上要考虑：某一侧为空数组，答案必须是空数组；同一个数字在一侧出现 3 次、另一侧出现 1 次，答案只能给 1 个；元素值域没有承诺很小，所以不能想当然地开一个定长计数数组。

解法：哈希表统计较短数组频率

核心思路

问题关键： 交集需要保留重复次数。对任意值 x，答案中它出现的次数应为两数组中出现次数的较小值，而不是只记录“出现过”。

为什么用计数哈希表： 暴力匹配要反复查找尚未使用的相同元素，时间为 $O(mn)$。将较短数组压缩成“值 → 剩余次数”，扫描另一数组时即可用均摊 $O(1)$ 的查询完成一次配对。

不变量： 扫描第二个数组的过程中，freq[x] 始终表示第一个数组中的 x 扣除已配对数量后的剩余额度。只有额度大于 0 才加入结果，并立即减 1。

正确性： 每次加入 x 都同时消耗两侧各一次出现，因此不会超过任一数组的频率；扫描结束后，第二个数组中所有能与剩余额度配对的 x 都已加入，数量恰好是两侧频率的较小值。先交换数组只改变扫描顺序，不改变交集。

解题步骤

  1. 若 nums1 更长，交换两个参数，保证哈希表建立在较短数组上。
  2. 遍历 nums1，统计每个值的出现次数。
  3. 遍历 nums2；当前值的剩余次数大于 0 时，将它写入结果并把次数减 1。
  4. 返回实际写入长度对应的结果。

口述示例： [4,9,5] 与 [9,4,9,8,4] 建表后，9 和 4 第一次出现时各消耗一个额度；后续 9、4 的额度已为 0，最终得到 [9,4]。

面试追问： 若两个数组已经有序，可用双指针在 $O(m+n)$ 时间、$O(1)$ 额外空间内完成；若只有一个超大数组无法整体载入，可让较小数组的计数表常驻内存，对大数组分块读取。

代码实现

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

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))$，计数表建立在较短数组上；不计返回结果。

关键点总结

  • 本题是多重集合交集，重复次数取两侧频率的较小值。
  • 计数值是会被消耗的额度，匹配后必须立即减 1。
  • 算法对输入对称时，让较短的一侧承担额外空间。
  • 已排序输入优先考虑双指针；无序输入用计数表避免额外排序。

易错点总结

  • 使用 Set：会把 [2,2] 错误去重成 [2]。
  • 匹配成功后不减次数：[1] 与 [1,1] 会多匹配一次。
  • 只判断 containsKey 而不判断次数是否为 0：已耗尽的键仍会被重复使用。
  • 假设值域很小而开定长计数数组：元素超出预设范围时会越界或浪费大量空间。

相似题目

题目 难度 考察点
349. 两个数组的交集 简单 集合语义去重，答案不保留重数
2215. 找出两数组的不同 简单 求双向差集而非交集，同样用集合而非计数
242. 有效的字母异位词 简单 要求两侧计数完全相等，而非取较小值
383. 赎金信 简单 单向包含判断，只需额度够不够，无需收集
88. 合并两个有序数组 简单 有序前提下的双指针归并，原地写入不用哈希
1. 两数之和 简单 哈希表存下标而非频率，配对目标是和