349. Intersection of two arrays

First, use two sets to store the elements in two arrays , Then traverse one of the sets , Determine whether each element is in another set , If the element is also in another collection , The element is added to the return value . The time complexity of this method can be reduced to O(m+n)

Sets are divided into three types ：

• std::set
  Underlying implementation ： Red and black trees
  Is it orderly ： Orderly
  Whether the value can be repeated ： no
  The query efficiency ：O(logn)
• std::multiset
  Underlying implementation ： Red and black trees
  Is it orderly ： Orderly
  Whether the value can be repeated ： yes
  The query efficiency ：O(logn)
• std::unordered_set
  Underlying implementation ： Hashtable
  Is it orderly ： disorder
  Whether the value can be repeated ： no
  The query efficiency ：O(1)

Sum up , Use unordered_set Efficiency is the highest .

class Solution {
    
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    
        unordered_set<int> result_set; 
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());// take num1 The data in is stored in nums1_set
        unordered_set<int> nums2_set(nums2.begin(), nums2.end());//nums1_set,nums2_set There are no repeated elements in 

        for (int num : nums2_set) // Traverse nums2_set： From an array nums2 Take out the elements in turn and assign them to integer variables nums, Loop execution for Middle sentence 
        {
    
            // If   There is ： lookup num Whether there is , There is an iterator that returns this element , There is no return nums1_set.end();
            if (nums1_set.find(num) != nums1_set.end()) // In collection 1 Search for , There are also collections found 2 This element in 
            {
    
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};