【代码随想录】LC 349. 两个数组的交集

前言

本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记，如有侵权，立即删除。

一、题目

1、原题链接

349. 两个数组的交集

2、题目描述

二、解题报告

1、思路分析

（1）由于题目中要求输出结果中的每个元素是唯一的。所以需要对结果进行去重，而又需要快速判断是否是两数组的交集。我们可以使用 unordered_set，其底层是哈希表，存/取时间为O(1)，既满足了存取效率，同时也满足了去重的要求。
（2）我们可以首先将数组1中的元素去重放到哈希表中，然后依次来遍历数组2中的元素，如果其在哈希表中存在，则为两数组的交集；否则，则不是。

2、时间复杂度

时间复杂度O(n)

3、代码详解

class Solution {
   
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
   
        unordered_set<int> res;    //存放结果
        unordered_set<int> temp(nums1.begin(), nums1.end());  //将nums1中元素去重存放到temp中
        //遍历nums2
        for (int num : nums2) {
   
            //如果nums2中元素在temp中存在，说明该元素是数组的交集
            if (temp.find(num) != temp.end()) {
   
                res.insert(num);
            }
        }
        return vector<int>(res.begin(), res.end());   //将结果类型强转为题目要求类型，返回结果
    }
};