LC349. 两个数组的交集

题目描述

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2： 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的 提示： 1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000

题目解析

题目在说什么

这道题其实是在问：给你两个数字组成的“集合”（数组），找出它们共同拥有的数字，而且每个数字只出现一次。比如你有一个班级的学号列表，另一个班级的学号列表，找出两个班级都有的学号，重复的只算一次。

举个例子：

• 第一个数组：[1,2,2,1]（注意有重复的1和2）
• 第二个数组：[2,2]
• 它们共同拥有的数字只有2，所以答案是[2]

另一个例子：

• 第一个数组：[4,9,5]
• 第二个数组：[9,4,9,8,4]
• 共同拥有的数字是4和9，顺序不重要，所以[4,9]或[9,4]都行

题目还给了提示：数组长度最多1000，数字范围0到1000，所以不用担心特别大的数据。

---

思路是怎么来的

想象你面前有两堆扑克牌，每堆都有一些数字，你想找出两堆里都有的数字（重复的只看一次）。你会怎么做？

最直接的办法：拿第一堆的每张牌，去第二堆里一张张翻，看有没有一样的。但这样很慢，比如第一堆有1000张，第二堆也有1000张，最坏情况要翻100万次（1000×1000）。

有没有更聪明的办法？如果你先把两堆牌按数字从小到大排好，就像整理书架一样，然后你同时从两堆的最左边开始看：

• 如果左边堆的牌数字小，那它肯定不可能在右边堆里找到一样的（因为右边堆后面的数字只会更大），所以左边堆的牌直接跳过，看下一张。
• 如果右边堆的牌数字小，同理，跳过右边堆的这张。
• 如果两张一样大，那就找到了一个共同数字，记录下来，然后两堆都跳过这张，继续看下一张。

这样你只需要把两堆牌各看一遍（最多2000次），就能找出所有共同数字，比100万次快多了。这就是排序+双指针的思路：先排序，再用两个指针分别指向两个数组的开头，通过比较大小来移动指针。

---

代码逐步拆解

我们来看参考代码（Java），我会一步步解释每行在干什么。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 1. 先排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        // 2. 准备结果数组
        int length1 = nums1.length;
        int length2 = nums2.length;
        // 结果数组最多不会超过较短的数组长度（因为交集元素个数不可能多于任何一个数组）
        int[] res = new int[length1 > length2 ? length2 : length1];

        // 3. 设置三个指针
        int index = 0;      // 指向结果数组，准备放找到的共同数字
        int index1 = 0;     // 指向nums1的当前位置
        int index2 = 0;     // 指向nums2的当前位置

        // 4. 开始遍历，只要两个指针都没越界
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1];
            int num2 = nums2[index2];

            if (num1 == num2) {
                // 找到了共同数字，但要确保不重复
                // 如果结果数组是空的（index==0），或者当前数字不等于结果数组最后一个数字，就加入
                if (index == 0 || num1 != res[index - 1]) {
                    res[index] = num1;
                    index++;  // 指针后移，准备放下一个
                }
                // 无论是否加入，两个数组的指针都要后移，因为当前数字已经处理过了
                index1++;
                index2++;
            } else if (num1 < num2) {
                // nums1的数字小，它不可能在nums2里找到匹配（因为nums2后面的数字更大）
                // 所以跳过nums1的当前数字
                index1++;
            } else {
                // nums2的数字小，跳过它
                index2++;
            }
        }

        // 5. 最后，结果数组res里前index个元素就是答案，需要截取出来
        // 因为res可能比实际结果长（我们一开始分配了最大可能长度）
        return Arrays.copyOfRange(res, 0, index);
    }
}

关键点解释：

• 为什么排序？ 排序后，两个数组的数字都从小到大排列，这样我们才能用“比较大小”来决定移动哪个指针，避免盲目搜索。