349. Intersection of Two Arrays

问题来自 349. Intersection of Two Arrays

---

好几种方法：

1. 用hashset（或者说hashmap）来做是最简单的。先把第一个array的所有element放到hashset里面（有的hashset允许它自己的element又重复的，有的hashset不允许，我用的c++的set它不会保留重复的element）,然后再for loop第二个array，检查它的每个element是不是在hashset里面。
2. 把两个array都sort，然后用两个pointer分别指向array，同步往后走，做判断

---

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> myset;
        for (int i = 0; i < nums1.size(); ++i) {
            myset.insert(nums1[i]);
        }
        
        vector<int> result;
        for(int i = 0; i < nums2.size(); ++i) {
            set<int>::iterator iterator = myset.find(nums2[i]);
            if (iterator != myset.end()) {
                result.push_back(nums2[i]);
                // Remove to avoid adding the same element.
                myset.erase(iterator);
            }
        }
        
        return result;
    }
};

---

2, sort

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
  
        vector<int> result;
        
        int size1 = nums1.size(), size2 = nums2.size();
        int i = 0, j = 0;
        while(i < size1 && j < size2) {
            if (nums1[i] == nums2[j]) {
                result.push_back(nums1[i]);
                // Now skip elements from both nums1 and nums2
                int tmp = i;
                while (i < size1 && nums1[tmp] == nums1[i]) {
                    ++i;
                }
                tmp = j;
                while ( j < size2 && nums2[tmp] == nums2[j]) {
                    ++j;
                }
            } else if (nums1[i] < nums2[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        
        
        return result;
        
    }
};