📃 题目描述

题目链接：349. 两个数组的交集 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

说明：

输出结果中的每个元素一定是唯一的。

我们可以不考虑输出结果的顺序。

🔔 解题思路

首先我们需要注意的是，两个数组的交集是不包含重复数字的，那最简单的，我们可以将两个数组的交集存在 Set 中，由 Set 来帮我们去重。

那这个题目其实我们需要两个 Set，整体思路如下：

• 先处理数组 nums1 将其存入一个 Set
• 遍历数组 nums2，若某个数字在 Set 中存在，则将其存入交集 Set 中
• 最后返回这个 Set 即可

另外，上一题我们说过，对于哈希表中的 key，如果哈希值比较连续且固定，我们可以用数组的下标来等同，那显然，对于这个题目，不适合用数组来代替哈希表。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }

        // 存储交集
        Set<Integer> resSet = new HashSet<>();

        // 存储 nums1
        Set<Integer> set = new HashSet<>();

        for (int i : nums1) {
            set.add(i);
        }

        for (int i : nums2) {
            if (set.contains(i)) {
                resSet.add(i);
            }
        }

        // set 转 数组
        int[] res = new int[resSet.size()];
        int index = 0;
        for (Integer i : resSet) {
            res[index ++] = i;
        }
        
        return res;
        // 或者直接 return resSet.stream().mapToInt(Integer::intValue).toArray();
    }
}

💥 复杂度分析

• 空间复杂度：用到了两个 Set 和一个数组，空间复杂度为 O(N)；
• 时间复杂度：遍历了一遍 nums1，遍历了一遍 nums2，最后 set 转数组的时候又遍历了一遍 Set，所以总的时间复杂度是 O(N)