My C++ Hash Table Solution

• ``````class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> ret;
unordered_set<int> set;
// hash the first array
for(auto n : nums1)
set.insert(n);
for(auto n : nums2) {
if(set.find(n) != set.end())  // found
{
set.erase(n);       // delete it from hash table
ret.push_back(n);
}
}
return ret;
}
};``````

• C++ Apply binary search on the longer array.

`````` vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int>& n1 = nums1.size() >= nums2.size() ? nums1 : nums2;
vector<int>& n2 = nums1.size() < nums2.size() ? nums1 : nums2;

sort(n1.begin(), n1.end());
sort(n2.begin(), n2.end());
vector<int> res;

for(auto n:n2){
if((res.empty() || res.back() != n) && binary_search(n1.begin(), n1.end(), n)){
res.push_back(n);
}
}

return res;
}``````

• yes, the time complexity of your solution is (m+n)log(n),but use hash table which is O(m+n).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.