LeetCode 350、两个数组的交集II

题目描述

你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2] 示例 2: 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]

提示： 1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000

题目解析

题目在说什么

这道题想让我们找出两个数组里“共同有的那些数字”，而且每个数字要出现几次呢？比如第一个数组里有 3 个“2”，第二个数组里有 2 个“2”，那交集里就只放 2 个“2”，因为“取较小的那个次数”。简单说，就是两个数组里都有的数字，按出现次数较少的那个数量拿出来。

举个例子：

• 数组1: [1,2,2,1] → 数字1出现2次，数字2出现2次
• 数组2: [2,2] → 数字2出现2次，数字1出现0次
• 交集结果: [2,2]（因为数字2在两个数组中都出现了，而且次数都是2，取较小值2；数字1只在第一个数组出现，不算）

思路是怎么来的

想象你在整理两个人的玩具箱。

• 第一个箱子里有：1号玩具2个，2号玩具2个。
• 第二个箱子里有：2号玩具2个。

你想知道“两个箱子里都有的玩具，并且每种玩具只拿较少的那个数量”。 你会怎么做？ 1. 先分别数一数每个箱子里每种玩具的数量。 2. 然后看哪些玩具是两个箱子都有的（比如2号玩具）。 3. 对于都有的玩具，取两个箱子中数量较少的那个（比如2号玩具，第一个箱子有2个，第二个箱子也有2个，取2个）。

计算机做这件事也一样：它需要先“数一数”每个数组里每个数字出现了几次，然后比较这些次数。 “数一数”这个动作，在编程里就是用“哈希表”（可以想象成一个本子，上面记着“数字→次数”的对应关系）。 所以思路就是：

• 先给第一个数组建一个“次数本子”。
• 再给第二个数组建一个“次数本子”。
• 然后看第一个本子里有哪些数字，如果第二个本子里也有，就取两个次数里较小的那个，把数字重复添加那么多次到结果里。

代码逐步拆解

我们来看参考代码，一行一行解释。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> count1 = new HashMap<>();
        Map<Integer, Integer> count2 = new HashMap<>();
        List<Integer> result = new ArrayList<>();

• 这里创建了两个“本子”（HashMap），分别叫 count1 和 count2，用来记录每个数字出现的次数。
• 还创建了一个“袋子”（ArrayList），叫 result，用来装最终要返回的那些数字。

        for (int num : nums1) {
            count1.put(num, count1.getOrDefault(num, 0) + 1);
        }

• 这一句是“数第一个数组里的数字”。
• 循环遍历 nums1 里的每个数字 num。
• count1.getOrDefault(num, 0) 意思是：从本子里查一下 num 出现过几次，如果没出现过就返回 0。
• 然后 +1，再放回本子里。
• 比如 nums1 = [1,2,2,1]：
• 遇到第一个1：count1里没有1，getOrDefault返回0，+1后变成1，put进去 → count1 = {1:1}
• 遇到第一个2：count1里没有2，变成1 → count1 = {1:1, 2:1}
• 遇到第二个2：count1里有2，值是1，+1后变成2 → count1 = {1:1, 2:2}
• 遇到第二个1：count1里有1，值是1，+1后变成2 → count1 = {1:2, 2:2}
• 这样 count1 就记录好了。

        for (int num : nums2) {
            count2.put(num, count2.getOrDefault(num, 0) + 1);
        }

• 完全一样的方法，给第二个数组 nums2 建本子。

        for (int key : count1.keySet()) {
            if (count2.containsKey(key)) {
                int commonCount = Math.min(count1.get(key), count2.get(key));
                for (int i = 0; i < commonCount; i++) {
                    result.add(key);
                }
            }
        }

• 现在开始找交集。
• count1.keySet() 拿到第一个本子里所有数字（比如 1 和 2）。
• 对每个数字 key，先看第二个本子里有没有这个数字（count2.containsKey(key)）。
• 如果有，就取两个次数里较小的那个（Math.min(count1.get(key), count2.get(key))），存到 commonCount 里。