给定两个数组 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</code"><!--=-->0 <= nums1[i], nums2[i] <="1000</code"><!--=-->
思考：
本题乍一看，与之前的1002. 查找共用字符十分相似，不同之处有两点：一是本题输出的结果不能重复，每个元素都要求是唯一的，二是本题的数组中不再是字符，二是数字，而数字的取值范围则是远大于1002题中的26个字符的。
但是由于这么做会产生极大的空间浪费，而且也有可能遇到数字取值范围不确定的情况，这个时候，我们就可以选用一种全新的哈希表类型，set哈希表进行求解。
数组型哈希表：
数组型哈希表是通过定义两个大小为1001的数组，对每个元素的出现次数进行记录，进而求解：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
if (nums1.size() == 0 || nums2.size() == 0)
{
return result;
}
int hash1[1001] = { 0 };
int hash2[1001] = { 0 };
for (int i = 0; i < nums1.size(); i++)
{
hash1[nums1[i]]++;
}
for (int i = 0; i < nums2.size(); i++)
{
hash2[nums2[i]]++;
}
for (int k = 0; k < 1001; k++)
{
hash1[k] = min(hash1[k], hash2[k]);
}
for (int i = 0; i < 1001; i++)
{
if (hash1[i] != 0)
{
result.push_back(i);
}
}
return result;
}
};
set哈希表：
set哈希表的使用就比较简便，利用了unordered_set容器，可以大大节省空间。当哈希值比较少，而且分散，跨度大时，很适合用这种形式的哈希表。
然而set哈希表也有其缺点，不仅占用空间比数组大，而且速度要比数组慢。
class Solution2 {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2) {
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
其中使用到了set容器中的find函数：
find(key);//查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
也使用到了C++11的新特性，即
for (int num : nums2)
等价于：
int num;
for(int i=0;i<num2.length;i++)
{
num=nums2[i];
}
参考：
Original: https://blog.csdn.net/weixin_51630192/article/details/127821826
Author: 一粒蛋TT
Title: 【LeetCode349. 两个数组的交集】——数组型哈希表，set型哈希表
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/659389/
转载文章受原作者版权保护。转载请注明原作者出处！