题目

力扣题目

给定两个整数数组 nums1 和 nums2，返回它们的交集。结果中的每个元素必须唯一，输出顺序不限。

示例 1：

Text
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

Text
输入：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

考察内容

  • 使用标记数组表示元素是否出现
  • 利用数据范围选择数据结构
  • 交集结果去重
  • 元素值与数组下标的区别
  • 哈希集合的通用解法

解题思路

标记数组

题目明确所有元素都位于 [0, 1000]，因此可以使用长度为 1001 的布尔数组 present：

  1. 遍历 nums1，令 present[value] = true；
  2. 遍历 nums2，若 present[value] 为 true，说明该值同时存在于两个数组中，将它加入答案；
  3. 加入答案后立刻令 present[value] = false，避免 nums2 中的重复值被再次加入。

以 nums1 = [1,2,2,1]、nums2 = [2,2] 为例：

  • 扫描 nums1 后，标记位置 1 和 2；
  • 扫描 nums2 的第一个 2，命中标记，加入结果并清除位置 2；
  • 扫描第二个 2 时标记已清除，因此不会重复加入。

⤢ 打开

  • 时间复杂度：O(n+m)O(n + m)
  • 空间复杂度：O(1)O(1)，标记数组大小固定为 1001

哈希集合

如果题目没有限制元素范围，可以将 nums1 放入 unordered_set，再遍历 nums2 查找交集。为了保证答案唯一，可以使用另一个集合保存结果，或者命中后从第一个集合中删除该值。

哈希集合解法的平均时间复杂度也是 O(n+m)O(n + m)，空间复杂度为 O(n)O(n)，适用范围更广。

代码演示

C++
std::vector<int> intersection(const std::vector<int>& nums1,
                              const std::vector<int>& nums2) {
    // 题目保证元素值位于 [0, 1000]
    std::array<bool, 1001> present{};

    for (int value : nums1) {
        present[value] = true;
    }

    std::vector<int> result;

    for (int value : nums2) {
        if (present[value]) {
            result.push_back(value);
            present[value] = false;  // 清除标记，保证结果唯一
        }
    }

    return result;
}

易错点

  • 使用循环下标进行标记：应该写 present[value] = true，而不是 present[i] = true；查找依据是元素值。
  • 标记数组未初始化：必须使用 present{} 将所有位置初始化为 false。
  • 结果没有去重：nums2 可能含有重复元素，命中后清除标记即可保证只输出一次。
  • 数组长度开成 1000：元素值可能等于 1000，因此需要 1001 个位置。
  • 认为结果顺序固定：题目允许任意顺序，不应依赖某一种排列进行判断。
  • 在元素范围未知时仍开巨大数组：值域很大或包含负数时，应改用哈希集合。

总结

本题利用较小且明确的值域，把“某个元素是否出现”映射为布尔数组中的一个位置。命中后清除标记，则同时完成交集判断和结果去重。

相关题目

    1. 两个数组的交集 II
    1. 快乐数
    1. 有效的字母异位词
    1. 查找共用字符