349. 两个数组的交集

首先使用两个集合分别存储两个数组中的元素，然后遍历其中的一个集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)

集合分为三种：

• std::set
  底层实现：红黑树
  是否有序：有序
  数值是否可以重复：否
  查询效率：O(logn)
• std::multiset
  底层实现：红黑树
  是否有序：有序
  数值是否可以重复：是
  查询效率：O(logn)
• std::unordered_set
  底层实现：哈希表
  是否有序：无序
  数值是否可以重复：否
  查询效率：O(1)

综上，使用unordered_set效率是最高的。

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());//将num1中的数据存入到nums1_set
        unordered_set<int> nums2_set(nums2.begin(), nums2.end());//nums1_set,nums2_set中都没有重复的元素了

        for (int num : nums2_set) //遍历nums2_set：从数组nums2依次取出元素赋值给整型变量nums，循环执行for中语句
        {
    
            //如果 存在：查找num是否存在，存在返回该元素的迭代器，不存在返回nums1_set.end();
            if (nums1_set.find(num) != nums1_set.end()) //在集合1中查找，发现也有集合2中的这个元素
            {
    
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};