前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

给定两个数组 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

1. 哈希表

思路（定义变量）

1. 定义两个unordered_set,一个用来给条件中的一个vector变量去重，一个用来接收去重的结果。

2. 本题思路分析：

1. 因为题目中输出结果中的每一个元素一定是唯一的，我们可以不考虑输出结果的顺序，想到可以借助unordered_set来实现对于结果的去重，并且这个set底层是哈希表实现，意味着其存储元素不按照输入顺序（但是这样的存储结构让他的查询、修改效率达到了O(1)）。
2. 具体实现查看卡哥教程（已经很详细了）

3. 算法实现

• 代码：

#include
#include
using namespace std;
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
	unordered_set<int> nums1_set(nums1.begin(),nums1.end());
	unordered_set<int> result_set;
	for(int n : nums2){
		if(nums1_set.find(n) != nums1_set.end()){
			result_set.insert(n);
		}
	}
	return vector<int>(result_set.begin(),result_set.end());
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4. 算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

5. 算法坑点

1. 对于set的操作（比如insert是加入新元素）不熟练。
2. 对于vector和set之间互相转化不熟练（初始化，有一个set函数set< int> s，vector< int> v(s.begin(),s.end()) ）。