@TOC
一、题目描述及思路讲解
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] <= 10002. 思路顺理和分析
- 题目意思很简单，就是给你两个数组，然后求他们的交集，也就是相同的元素。首先我们应该考虑要使用那种数据结构，可以看到，之前的题解都是没有贴上数据范围的，这题我在题目描述的时候加上了一个提示，也就是两个数组的数据范围，因为这个数据范围是力扣官方近期修改后的数据，原本这个数据是比较大的，我也不太记得了，之前做的时候是10^9^，但是从现在的数据范围可以看出，只是1 - 1000这样的范围，其实这个在力扣的题目中还是比较小的数据，因为关注到了这一点，因此我又想出了一种方案，一开始用的是==哈希表==解决，因为考虑到数据比较大，但是现在数据范围改小了，因此考虑==数组==会比较适合一些，然后我就根据数组又萌生出了一种==双指针==的思路，也是比较巧妙的一种方法，因此作为经典题型分享给大家:raised_hands:
二、方法罗列及步骤详解
方法一【哈希表】
结构选择与分析
对于给你一个元素，去判断在这个集合里是否出现过，这种题型，都应该第一时间想到哈希表，因为其实最搞笑的，接着既然是求解集合相关的问题，那就想到set，但是有关set的哈希结构有三种
| 集合 | 底层实现 | 是否有序 | 是否可重复 | 数值可否更改 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | 否 | O(nlogn) | O(nlogn) |
| std::multiset | 红黑树 | 有序 | 是 | 否 | O(nlogn) | O(nlogn) |
| std::unordered_set | 哈希表 | 无序 | 是 | 否 | O(1) | O(1) |
set和multiset底层实现都是 红黑树，unordered_set的底层实现是 哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set，具体的详解如何选择哈希结构我在 一文带你快速入门【哈希表】中有详解介绍过，如果不太清楚的小伙伴可以再去看看:runner:
- 具体的思路就是将题目给出的nums1放到哈希集合unordered_set中，然后去遍历nums2这个数组，看看在nums2中是否有我们之前存在哈希集合中的相同的数，为了更加生动地理解，特此画了张逻辑图给大家看，可以看出，在转化为unordered_set是自动进行了去重操作，因为集合存在一个互异性的原理，一个集合中不可以有重复的元素，因此用此哈希结构都不需要我们手动进行去重操作
- 讲解完具体思路后，C++代码如下
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
unordered_set<int> num(nums1.begin(),nums1.end()); //把nums1中数放入num集合
//遍历nums2数组，与num集合做比较
for(int i : nums2)
{
if(num.find(i) != num.end())
//没有到num的结尾就发现了异常情况
result.insert(i); //将交集元素放入result集合
}
//最后以一个vector容器的形式返回
return vector<int>(result.begin(),result.end());
}
};- num是暂时存放nums1的集合，result是存放结果集的，然后在对nums2进行遍历的时候，用find()函数去寻找是否有符合条件的元素，若是没到结尾便发现了有相同元素，那此元素即为交集，insert()进result结果集中，最后要开辟一个vector容器去返回结果，将result的开始迭代器和结束迭代器传入即可
此题的提交结果
方法二【数组】
- :star:开头提到，因为官方修改了数据范围，因此考虑到使用数组更为优化。逻辑思路还是类似，首先要定义一个大小大于1000的数组大小值，==将里面的数据都初始化为0，这点很重要==，否则初始化的数据会是随机值，会影响最后的结果输出然后通过循环先去遍历nums1，将出现过的数所对应的数组都置为1，接着就是去遍历nums2，判断是否有相等的数字，若是有，则将其放入哈希集合中，最后还是一样定义一个vector容器返回即可
- 具体C++代码如下
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
int hash[1004]{}; //采取数组存储
for(int i : nums1)
hash[i] = 1;
for(int j : nums2)
if(hash[j] == 1)
result.insert(j);
return vector<int>(result.begin(),result.end());
}
};这是数组解法的通过效率，可以看出空间复杂度低了许多
方法三【双指针】
- 最后一个方法也是我根据数组萌生出来的一个方法，那就是利用双指针的思路，虽然效率不是很高，但也是一种思路，值得一试:dizzy:
- 具体的思路就是先要手动把两个数组排个序，然后定义两个分别指向各自数组的指针，去一个个迭代遍历，可见快排sort()的时间复杂度为O(nlogn)，已经需要一部分的时间，所以效率不会太高，但是不需要哈希表去维护数组和集合，也算是省去了一些空间，因为空间与时间是不可兼得的，很少有这样的解法
具体遍历过程
由于动画太快了，因此我一步步分开细讲:mag:
- 首先就是初始化时的样子
- 当两个值相等时，此数就为待插元素，就判断若还没到达结尾或者此数是否与上一个放入结果集中的数一样，如果都不符合，就讲此数放入结果集，然后两个指针后移，此时4 < 5，故index2后移
- 当碰到两个数不一样时，就判断是n1大还是n2大，比较完后较小数字的指针后移一位
- 此时5 < 8比较小，index1后移
。。。
- 遍历到此处时，由于两数相同，既没有到结果集末尾，上一个结果集中的数又不是9，因此将9放入结果集中
- 最后，当其中任意一指针超过当前数组长度时，便退出循环，返回结果集
- 以下是C++代码展示
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//对两个数组进行排序
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int index1 = 0,index2 = 0; //指向两个数组的指针
int l1 = nums1.size();
int l2 = nums2.size(); //获取两数组的长度
vector<int> result;
while(index1 < l1 && index2 < l2)
{ //index1、index2从0开始，因此不能遍历到l1和l2，否则会造成数组越界
int n1 = nums1[index1];
int n2 = nums2[index2];
if(n1 == n2){
if(!result.size() || n1 != result.back()){
//若还没到结果集结尾或者与上一个插入的容器中的值不同
result.push_back(n1);
}
index1++;
index2++; //双指针的共同后移
}else if(n1 < n2){
index1++;
}else{
index2++;
}
}
return result;
}
};本题的通过效率
三、归纳总结与拓展
看完了此题的三种解法后，你是否又多了几种解题的思路呢，本题是哈希表章节中比较经典的题目，虽然并不是很难，但是想要有一个最优解却不易，以下也是哈希表相关的例题，大家在学习了哈希表的基础知识后多去刷刷题，对知识的理解会更加深刻，关注我，后续会有更精彩的题解奉上:boom:
以下是我开创的社区，感兴趣的小伙伴们可以加入进来一起交流学习，解决编程的难题
我的社区：:fire:烈火神盾:fire:
