算法-哈希表篇02-两个数组的交集
两个数组的交集
力扣题目链接
题目描述
给定两个数组 nums1 和 nums2 ，返回它们的交集
输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。
解题思路
我们使用一个哈希表来存储nums1中的元素，然后遍历数组nums2，并查找哈希表中是否含有该元素，如果含有则是两者交集，存储在ans数组中。
题解
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> ans;
unordered_set<int> us(nums1.begin(), nums1.end());
for(int x : nums2){
if(us.count(x)){
ans.push_back(x);
us.erase(x);
}
}
return ans;
}
};
总结
主要是要理解，这道题如果使用双循环遍历两个数组也是可以的，但是这样的作法时间复杂度为O(n2)n的平方，使用哈希表，查询效率为O(1)所以，总体的时间复杂度为O(n)，在时间上优化了算法。