【C算法打怪专栏】LeetCode 349. 两个数组的交集哈希集合解法总结一、 题目链接LeetCode 官方网址LeetCode 349. 两个数组的交集二、 核心思路去重与匹配题目要求输出的交集结果中每个元素必须是唯一的且不限输出顺序。哈希集合unordered_set优化将其中一个数组如num1的元素全部放入unordered_set中利用其特性自动去重。遍历另一个数组如num2检查每个元素是否存在于哈希表中。防重关键erase一旦在哈希表中找到交集元素立即将其放入结果集并使用us.erase()将其从哈希表中移除防止num2中重复的相同元素导致结果集中出现重复。三、 C 标准精简源码#includevector#includeunordered_setusingnamespacestd;classSolution{public:vectorintintersection(vectorintnum1,vectorintnum2){// 1. 将 num1 的元素全部放入哈希集合中自动去重unordered_setintus(num1.begin(),num1.end());vectorintres;// 2. 遍历 num2 寻找交集for(intnum:num2){if(us.find(num)!us.end()){res.push_back(num);us.erase(num);// 核心移除已匹配元素防止 num2 的重复元素导致结果重复}}returnres;}};四、 复杂度分析时间复杂度O ( N M ) O(N M)O(NM)其中N NN和M MM分别是两个数组的长度。将num1放入哈希表的时间复杂度是O ( N ) O(N)O(N)遍历num2并进行查找和擦除的时间复杂度是O ( M ) O(M)O(M)。空间复杂度O ( N ) O(N)O(N)最坏情况下需要将num1的所有不重复元素全部存入哈希集合中。
