力扣每日一题-第17天-349.两个数据的交集

2022.6.9今天你刷题了吗？

---

题目：

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

分析：

给定两个数组，找出里面具有相同的元素。

对于相同，也就是重复元素，哈希是个好方法！所以我们的思路是先把两个数组各种插入到另外一个map中，然后把重复元素去掉（这里也可以用set），然后再把这两个map插入到 另外一个map中，再次判断最后一个map中键值对为2的，那么就是重复元素。

解析：

1.哈希暴力

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        map<int, int>m1;
        map<int, int>m2;
        unordered_map<int, int>m3;
        vector<int>v1;
        for (auto num : nums1)
        {
            if (m1[num])
            {

            }
            else
            {
                m1[num]++;
                m3[num]++;
            }
        }
        for (auto num : nums2)
        {
            if (m2[num])
            {

            }
            else
            {
                m2[num]++;
                m3[num]++;
            }
        }
        for (auto num : m3)
        {
            if (num.second == 2)
            {
                v1.push_back(num.first);
            }
        }

        return v1;
    }
   
};

2.哈希优化

这里我们先把一个数组处理存入map中，然后判断另外一个数组的数是否存在该map中

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        std::unordered_map<int, int> map;
        vector<int> ans;
        for (int i = 0; i < nums1.size(); i++) {
            map[nums1[i]] = 1;
        }

        for (int i = 0; i < nums2.size(); i++) {
            if (map[nums2[i]] == 1) {
                //因为没有排序，所以重复了要清除
                map[nums2[i]] = 0;
                ans.push_back(nums2[i]);
            }
        }
        return ans;
    }
};