哈希表2：两个数组的交集（349）

本题如下：（链接：https://leetcode.cn/problems/intersection-of-two-arrays/submissions/）

题目：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

其中，1 <= nums1.length, nums2.length <= 1000，0 <= nums1[i], nums2[i] <= 1000。

说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

思路：

写这道题目的主要目的是要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序。

这道题用暴力的解法时间复杂度是O(n^2)，于是我们想到使用哈希法进一步优化。

但是要注意，这道题能够使用数组来做哈希的题目，是因为题目都限制了数值的大小。

但如果这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set 。

关于set，C++ 给提供了如下三种可用的数据结构：（1）std::set（2）std::multiset（3）std::unordered_set

其中，std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表。

使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以这道题我们选择unordered_set。

思路如下图所示：

这样就可以给出使用set的C++程序：

 1 class Solution {
 2 public:
 3     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 4         unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
 5         unordered_set<int> nums_set(nums1.begin(), nums1.end());
 6         for (int num : nums2) {
 7             // 发现nums2的元素 在nums_set里又出现过
 8             if (nums_set.find(num) != nums_set.end()) {
 9            //find(返回值是一个迭代器，并不是1或0，当未找到时，返回num.end()迭代器，所以不相等时为找到
10                 result_set.insert(num);
11             }
12         }
13         return vector<int>(result_set.begin(), result_set.end());
14     }
15 };    

需要注意的是，并不是任何情况都可以用set，直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

因此，使用set还是数组也得考虑实际情况。

由于本题的数组都是1000以内的，所以就可以使用数组来做哈希表了

对应C++代码如下：

 1 class Solution {
 2 public:
 3     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 4         unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
 5         int hash[1005] = {0}; // 默认数值为0
 6         for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
 7             hash[num] = 1;
 8         }
 9         for (int num : nums2) { // nums2中出现话，result记录
10             if (hash[num] == 1) {
11                 result_set.insert(num);
12             }
13         }
14         return vector<int>(result_set.begin(), result_set.end());
15     }
16 };

下面给出Java版本：

 1 import java.util.HashSet;
 2 import java.util.Set;
 3 
 4 class Solution {
 5     public int[] intersection(int[] nums1, int[] nums2) {
 6         if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
 7             return new int[0];
 8         }
 9         Set<Integer> set1 = new HashSet<>();
10         Set<Integer> resSet = new HashSet<>();
11         //遍历数组1
12         for (int i : nums1) {
13             set1.add(i);
14         }
15         //遍历数组2的过程中判断哈希表中是否存在该元素
16         for (int i : nums2) {
17             if (set1.contains(i)) {
18                 resSet.add(i);
19             }
20         }
21         //将结果几何转为数组
22         return resSet.stream().mapToInt(x -> x).toArray();
23     }
24 }