给你两个整数数组nums1和nums2，请你以数组形式返回数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例：
输入：nums1 = [1, 2, 2, 1], nums2 = [2, 2]
输出：[2, 2]
思路一：排序+双指针
我们可以先将所给两个数组进行排序，之后用双指针遍历这两个有序序列，遍历过程如下：
- 若两个指针指向的元素不相等，则小的指针往后走。
- 若两个指针指向的元素相等，则该元素属于交集，两个指针同时往后走。
- 若其中一个序列走完了，则遍历结束。
代码一：
//排序+双指针
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
//1、将nums1和nums2分别进行排序
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
//2、使用双指针找出num1和nums2的交集
vector<int> vRet;
int len1 = nums1.size(), len2 = nums2.size();
int pos1 = 0, pos2 = 0;
while (pos1 < len1&&pos2 < len2)
{
if (nums1[pos1] < nums2[pos2]) //两个指针指向的元素不相等
{
pos1++; //小的往后走
}
else if (nums2[pos2] < nums1[pos1]) //两个指针指向的元素不相等
{
pos2++; //小的往后走
}
else //两个指针指向的元素相等
{
vRet.push_back(nums1[pos1]); //该元素属于交集
//两个指针一起往后走
pos1++;
pos2++;
}
}
return vRet;
}
};
思路二：哈希表
对于该题目，我们可以借助一个哈希表来求解，步骤分为两步：
- 将元素个数较少的数组先放入哈希表，统计出每个元素对应的出现次数。
- 遍历另一个数组，找出两个数组的交集。
遍历另一个数组，利用哈希表找两个数组的交集时，具体的查找方法如下：
- 如果遍历到的元素在哈希表中出现，则该元素属于交集，并将哈希表中该元素出现的次数减少一次，如果哈希表中该元素出现的次数减为0，则将该元素从哈希表中移除。
- 如果遍历到的元素没有在哈希表中出现，则继续遍历下一个元素。
这其实就是将一个数组当中的元素先用哈希表记录下来，然后遍历另一个数组的元素，对比哈希表当中的数据找到可以进行抵消的元素，可以抵消的元素即是这两个数组的交集。
说明一下：选择将元素个数较少的数组放入哈希表，可以降低空间复杂度。
代码二：
//哈希表
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
//为了降低空间复杂度，应该先将元素个数较少的数组放入哈希表
if (nums1.size() > nums2.size())
{
return intersect(nums2, nums1);
}
//1、将nums1中的每个数字以及对应出现的次数放入哈希表中
unordered_map<int, int> um;
for (auto e : nums1)
{
um[e]++;
}
//2、遍历nums2，找出nums1和nums2的交集
vector<int> vRet;
for (auto e : nums2)
{
if (um.count(e)) //该元素在哈希表中
{
vRet.push_back(e); //该元素属于交集
um[e]--; //减少该元素在哈希表中出现的次数
if (um[e] == 0) //该元素的次数已经变为0了
{
um.erase(e); //将该元素从哈希表中删除
}
}
}
return vRet;
}
};