349 两个数组的交集
哈希表
数组
本题后面 力扣改了 题目描述 和 后台测试数据,增添了 数值范围:
- 1 <= nums1.length, nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 1000
所以就可以 使用数组来做哈希表了, 因为数组都是 1000以内的。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
// 对答案去重
unordered_set<int> ans;
int hashMap[1005] = {0};
for (int num : nums1) {
hashMap[num] = 1;
}
for (int num : nums2) {
if (hashMap[num] == 1)
ans.insert(num);
}
return vector<int>(ans.begin(), ans.end());
}
};
unordered_set
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> ans;
unordered_set<int> hashMap;
for(int num : nums1){
hashMap.insert(num);
}
for(int num : nums2){
if(hashMap.find(num) != hashMap.end())
ans.insert(num);
}
return vector<int>(ans.begin(),ans.end());
}
};
复杂度分析:
- 时间复杂度: \(O(n)\)
- 空间复杂度: \(O(n)\)