两个数组的交集（暴力、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分别是两个数组的长度。