LeetCode 349. 两个数组的交集

约 5 分钟
文章信息 19 个分类 5 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 历史考题 20-50 字节跳动 微软 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 网易 虾皮 作业帮
标签
数组 哈希表 排序 双指针 二分查找
目录

题目描述

✅ 349. 两个数组的交集

image-20230307195920366

题意分析

给两个整数数组，要返回同时出现在两个数组里的数字。这里的「交集」是集合意义上的：输入里某个数字出现多少次都不影响结果，它在答案中只能出现一次。

约束里有三个信号。第一，题目明确说明结果可以按任意顺序返回，这就免去了排序或保序的负担，也提示可以用无序容器。第二，两个数组的长度上界都是 1000，数值范围是 0 到 1000，规模很小，线性额外空间毫无压力。第三，输入数组本身可能含重复元素，这正是「结果需要去重」的来源，也是本题唯一真正的陷阱。

边界方面：两个数组都至少含 1 个元素，不必处理空输入；但交集本身可以为空，此时应返回长度为 0 的数组而不是 null。另外，输入数组是无序的，不能假设有序而直接上双指针。

解法：哈希集合，命中后删除

核心思路

题目要的是集合意义上的交集：只关心一个值是否同时出现，不关心出现次数和输出顺序。排序后用双指针能做，但会把时间提高到 $O(m\log m+n\log n)$；哈希集合更贴合「存在性查询」，平均可以线性完成。

先把较短数组的不同元素放入集合 candidates，再扫描较长数组。若 candidates.remove(num) 成功，说明该值同时出现在两边，而且此前还没有输出，于是把它写入答案。命中后直接删除，比再维护一个结果集合更省：同一个值以后再次出现时，删除会失败，自然不会重复写入。

循环不变量是：扫描较长数组的任意前缀后，答案恰好包含该前缀与短数组的交集；candidates 则保存短数组中尚未输出的不同值。因此写入的值一定属于交集且只写一次；扫描结束后，所有属于完整交集的值也一定已经被写入。

解题步骤

  1. 若 nums1 更长就交换两个数组，保证集合建立在较短数组上。
  2. 把较短数组的元素加入 candidates，集合自动去掉其内部重复值。
  3. 扫描较长数组；只有 remove 返回 true 时，才把当前值写入结果。
  4. 返回结果数组的有效前缀，题目允许任意顺序，无需额外排序。

例如 [1, 2, 2, 1] 与 [2, 2]：集合初始为 {2}。第一个 2 命中并被删除，答案加入 2；第二个 2 已无法再次命中，最终得到 [2]。

代码实现

import java.util.*;

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))$。集合建在较短数组上，答案长度也不会超过较短数组的不同元素个数。

关键点总结

  • 先确认题目要「去重后的交集」，若要保留重复次数，应改用计数哈希表。
  • 集合建在较短数组上，时间不变，但额外空间更稳。
  • remove 同时完成「是否存在」和「防止重复输出」两个动作，这是本解法的关键。
  • 正确性依赖的核心不变量是：答案保存已扫描部分的交集，集合保存尚未输出的候选值。

易错点总结

  • 只判断 contains 而不删除或不另行去重：[2, 2] 与 [2, 2] 会错误输出两个 2。
  • 把当前值无条件加入候选集合：[1] 与 [2, 2] 会让第二个 2 错误命中。
  • 返回整个临时数组而不是有效前缀：交集较小时，尾部默认的 0 会混入答案。
  • 直接在无序输入上使用双指针：大小比较不能指导指针移动，会漏掉交集元素。

相似题目

题目 难度 考察点
1. 两数之和 简单 哈希表存的是「值到下标」的映射，边遍历边查而非分两轮
128. 最长连续序列 中等 同样用集合做 $O(1)$ 查询，但需只从序列起点向后扩展才能保住线性
202. 快乐数 简单 集合用于检测循环而非求交，也可换成快慢指针省掉额外空间
217. 存在重复元素 简单 只需判断插入是否失败即可提前返回，无需保留完整集合
350. 两个数组的交集 II 简单 要保留重复次数，须用计数哈希表取两边出现次数的较小值