两个数组的交集 | LeetCode-349 | 哈希集合 | 哈希数组 | 双指针 | 四种解法

再说一遍，能用哈希集合做的，哈希数组也有可能做出来！

---

LeetCode链接：349. 两个数组的交集

---

1.题目描述

给定两个数组 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

2.题解

2.1 直接法(暴力解法)-哈希集合

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 创建两个 HashSet，用于存储 nums1 和 nums2 中的所有元素
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();

        // 将 nums1 中的所有元素添加到 set1 中
        for (int num : nums1) {
            set1.add(num);
        }

        // 将 nums2 中的所有元素添加到 set2 中
        for (int num : nums2) {
            set2.add(num);
        }

        // 计算 set1 和 set2 的交集，并返回结果
        return getIntersection(set1, set2);
    }

    // 计算两个集合的交集
    public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
        // 如果 set1 的大小大于 set2，交换它们的位置以减少遍历次数
        if (set1.size() > set2.size()) {
            return getIntersection(set2, set1);
        }

        // 创建一个 HashSet 存储交集元素
        Set<Integer> intersectionSet = new HashSet<Integer>();

        // 遍历 set1，将同时存在于 set1 和 set2 中的元素添加到 intersectionSet 中
        for (int num : set1) {
            if (set2.contains(num)) {
                intersectionSet.add(num);
            }
        }

        // 将交集集合转换为数组
        int[] intersection = new int[intersectionSet.size()];
        int index = 0;
        for (int num : intersectionSet) {
            intersection[index++] = num;
        }

        return intersection;
    }
}

2.2 哈希集合优化

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 创建一个 HashSet 存储 nums1 中的所有元素，以去除重复并快速查找
        Set<Integer> set = new HashSet<>();

        // 将 nums1 中的每个元素添加到 HashSet 中
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }

        // 创建一个 HashSet 存储结果，记录 nums2 中与 nums1 交集的元素
        Set<Integer> resultSet = new HashSet<>();
        for (int i = 0; i < nums2.length; i++) {
            // 如果 nums2 的当前元素在 nums1 的集合中存在，则添加到结果集合中
            if (set.contains(nums2[i])) resultSet.add(nums2[i]);
        }
		
        // 将 resultSet 集合转换为数组
        // 方式1：手动遍历 resultSet 将其转换为数组
        int[] result = new int[resultSet.size()];
        int i = 0;
        for (int num : resultSet) {
            result[i++] = num;
        }
        
        // 方式2：使用 Stream API 将 resultSet 转换为数组
        // result = resultSet.stream().mapToInt(Integer::intValue).toArray();
        
        return result;
    }
}

2.3 哈希数组

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 创建两个大小为 1001 的数组，用于记录 nums1 和 nums2 中元素的出现情况
        int[] arr1 = new int[1001];
        int[] arr2 = new int[1001];

        // 遍历 nums1，记录每个元素的出现次数
        for (int i = 0; i < nums1.length; i++) {
            arr1[nums1[i]]++;
        }

        int count = 0; // 记录交集元素的个数
        // 遍历 nums2，检查元素是否存在于 nums1 中且未被记录到 arr2 中
        for (int i = 0; i < nums2.length; i++) {
            if (arr1[nums2[i]] != 0 && arr2[nums2[i]] == 0) {
                count++; // 找到一个交集元素，计数器加 1
                arr2[nums2[i]]++; // 标记该元素已被记录
            }
        }

        // 创建一个数组用于存储交集结果
        int[] result = new int[count];
        int index = 0;
        // 遍历 arr2，将交集元素添加到结果数组中
        for (int i = 0; i < arr2.length; i++) {
            if (arr2[i] != 0) result[index++] = i;
        }

        return result;
    }
}

2.4 排序+双指针

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 首先对两个数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        // 获取两个数组的长度
        int length1 = nums1.length, length2 = nums2.length;
        
        // 创建一个数组，用于存储交集元素，大小为两个数组长度之和（确保有足够空间）
        int[] intersection = new int[length1 + length2];
        
        // 用于跟踪结果数组的当前位置
        int index = 0;
        
        // 用于遍历 nums1 和 nums2 的索引
        int index1 = 0, index2 = 0;
        
        // 当两个数组都没有遍历完时，执行以下操作
        while (index1 < length1 && index2 < length2) {
            // 取出当前 index1 和 index2 所指向的元素
            int num1 = nums1[index1], num2 = nums2[index2];
            
            // 如果两个元素相等，说明找到了一个交集元素
            if (num1 == num2) {
                // 保证交集数组中元素的唯一性
                if (index == 0 || num1 != intersection[index - 1]) {
                    intersection[index++] = num1; // 将元素添加到交集数组中
                }
                index1++; // 移动 nums1 的指针
                index2++; // 移动 nums2 的指针
            
            // 如果 num1 小于 num2，则移动 nums1 的指针
            } else if (num1 < num2) {
                index1++;
            
            // 如果 num1 大于 num2，则移动 nums2 的指针
            } else {
                index2++;
            }
        }
        
        // 将交集数组的有效部分复制到一个新的数组中并返回
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

2.5 JS语法糖

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    // 将两个数组转换为 Set 集合，自动去重
    let set1 = new Set(nums1);
    let set2 = new Set(nums2);

    // 使用 Array.from 和 filter 结合来获取两个 Set 集合的交集
    return [...set1].filter(num => set2.has(num));
};