349. Intersection of Two Arrays

O(m + n)

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s(nums1.begin(), nums1.end());
        vector<int> res;
        for (int n : nums2) {
            if (s.find(n) != s.end()) {
                res.push_back(n);
                s.erase(n); // if nums2 has multiple copy of n, then the following instances cannot be found any more, in order to avoid duplicate push back
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, bool> m;
        for (int x : nums1) {
            m[x] = true;
        }
        vector<int> res;
        for (int x : nums2) {
            if (m[x]) {
                res.push_back(x);
                m[x] = false; // if nums2 has multiple copy of x, then the following instances cannot be found any more, in order to avoid duplicate push back
            }
        }
        return res;
    }
};