两个数组的交集（暴力、set、哈希）

一.题目

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

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

二.题目解析+思路

暴力枚举：

首先遍历第一个数组 nums1，然后对于 nums1 中的每个元素，再遍历第二个数组 nums2。如果找到相同的元素，并且这个元素还没有被添加到结果数组 result 中，就将其添加到 result 中。

时间复杂度是：O(n×m)

set优化:

利用set优秀的自动去重功能简化做题步骤。

哈希表：

思路和set差不多，但效率更高。

三.代码示例

暴力：

class Solution 
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<int> result;
        for (int i = 0; i < nums1.size(); ++i) 
        {
            for (int j = 0; j < nums2.size(); ++j) 
            {
                if (nums1[i] == nums2[j]) 
                {
                    // 检查是否已经添加到结果中，避免重复
                    bool found = false;
                    for (int k = 0; k < result.size(); ++k) 
                    {
                        if (result[k] == nums1[i]) 
                        {
                            found = true;
                            break;
                        }
                    }
                    if (!found) 
                    {
                        result.push_back(nums1[i]);
                    }
                }
            }
        }
        return result;
    }
};

首先遍历第一个数组 nums1，然后对于 nums1 中的每个元素，再遍历第二个数组 nums2。如果找到相同的元素，并且这个元素还没有被添加到结果数组 result 中，就将其添加到 result 中。

这种方法的时间复杂度是 O(n×m)，其中 n 和 m 分别是两个数组的长度。

 set:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        set<int> a1(nums1.begin(),nums1.end());
        set<int> a2(nums2.begin(),nums2.end());

        vector<int> v;

        for(auto x:a1)
        {
            if(a2.count(x))
            {
                v.push_back(x);
            }
        }
        return v;
    }

};

代码讲解： 

1. 将数组转换为 set：

   使用 set<int> 将 nums1 和 nums2 分别转换为两个 set，命名为 a1 和 a2。这一步自动去除了数组中的重复元素，并允许快速查找。

2. 初始化结果向量：

   创建一个 vector<int> 类型的结果向量 v，用于存储最终的交集结果。

3. 遍历第一个 set：

   使用范围 for 循环遍历 a1 中的每个元素 x。

4. 检查元素是否在第二个 set 中：

   对于 a1 中的每个元素 x，使用 a2.count(x) 检查该元素是否存在于 a2 中。如果存在（即 count 返回值大于0），则将该元素添加到结果向量 v 中。

5. 返回结果：

   遍历完成后，返回包含交集元素的结果向量 v。

 哈希：

class Solution {
public:
   vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
   {
    unordered_set<int> s(nums1.begin(), nums1.end());
    vector<int> result;
    for (int num : nums2) 
    {
        if (s.count(num)) 
        {
            result.push_back(num);
            s.erase(num); // 确保每个元素只出现一次
        }
    }
    return result;
   }
};

首先将第一个数组nums1的所有元素存入一个哈希表s中。然后遍历第二个数组nums2，如果nums2中的元素在哈希表s中存在，就将其添加到结果数组result中，并从哈希表中删除该元素，以确保每个元素只出现一次。这种方法的时间复杂度为O(n + m)，其中n和m分别是两个数组的长度。