leetcode刷题记录——（十六）349. 两个数组的交集

 （一）问题描述

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/intersection-of-two-arrays/       给定两个数组 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. 每个元素是唯一的；

2. 不考虑输出结果的顺序；

以上满足集合（set）的特征，可以考虑使用set来解决问题，在Java中对应Hashset。

（三）解决思路

1. 创建一个集合set1，将nums1的元素存储进去。这个过程可以将nums1所有元素都去重，减少操作。

2. 再创建一个新的集合resSet用来存储计算结果。利用contains()方法逐个判断nums2的元素是否出现在set1中，如果是，则添加仅resSet。

3. 利用一下代码将resSet转换为结果数组。也可以再创建一个数组存储结果并返回。

public int[] intersection(int[] nums1, int[] nums2) {HashSet<Integer> set1=new HashSet<Integer>();HashSet<Integer> resSet=new HashSet<Integer>();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();//直接将集合转化为数组/*int[] arr = new int[resSet.size()];//创建新数组用来存储结果int j = 0;for(int i : resSet){arr[j++] = i;}return arr;*/}

 （四）扩展

（1）数组的存储空间是连续的。如果哈希值少、分散、跨度大，那么使用数组就会造成极大的空间浪费。

（2）哈希问题不是任何时候都是使用set更好。 跟数组相比，set占用空间大，而且耗时长，每一次把数值映射到key上都需要进行哈希计算，当数据量大时耗时尤其明显。

         这个题目的提示当中给出了数组元素的取值范围是1-1000，所以也是可以用数组方法来解决的。

public int[] intersection(int[] nums1, int[] nums2) {int[] hash1 = new int[1001];int[] hash2 = new int[1001];for(int i : nums1)hash1[i]++;for(int i : nums2)hash2[i]++;List<Integer> resList = new ArrayList<>();for(int i = 0; i < 1001; i++)if(hash1[i] > 0 && hash2[i] > 0)resList.add(i);int index = 0;int res[] = new int[resList.size()];for(int i : resList)res[index++] = i;return res;}