Leetcode的AC指南 —— 哈希表：349. 两个数组的交集

摘要：
Leetcode的AC指南 —— 哈希表：349. 两个数组的交集。题目介绍：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

文章目录

• 一、题目
• 二、解析
• • 1、使用Int数组创建一个哈希表
  • 2、用HashSet作为哈希表

一、题目

---

题目介绍：给定两个数组 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、使用Int数组创建一个哈希表

public static int[] intersection(int[] nums1, int[] nums2) {
        int[] record = new int[10001];
        // 创建一个哈希表，默认值为0

        for(int i = 0; i < nums1.length; i++){
            // 将nums1中的元素放入哈希表中，标记为1
            record[nums1[i]] = 1;
        }
        for(int i = 0; i < nums2.length; i++){
            // 如果num2中的元素在nums1中，则标记为-1
            if(record[nums2[i]] == 1)
                record[nums2[i]] = -1;
        }

        // 哈希表中，值为-1为两个数组的交集
        List<Integer> result = new ArrayList<>();
        for(int i = 0; i <= 1000; i++){
            if(record[i] == -1) result.add(i);
        }

        // 将ArrayList转为数组输出。
        int[] re = new int[result.size()];
        int i = 0;
        for(int r : result){
            re[i++] = r;
        }

        return re;
    }

时间复杂度: O(m + n)
空间复杂度: O(n)

2、用HashSet作为哈希表

public static int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();

        for (int i : nums1) {
            set1.add(i);
        }
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        return resSet.stream().mapToInt(x -> x).toArray(); //set集合转换为数组
    }