題目

給定兩個數組，編寫一個函數來計算它們的交集。

1、暴力雙for循環

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> result;vector<int> res;if(nums1.size()==0 || nums2.size()==0) return result;for(int i=0;i<nums1.size();i++){for(int j=0;j<nums2.size();j++){if(nums1[i] ==nums2[j]) res.push_back(nums1[i]);}}if(res.size()==0) return result;sort(res.begin(),res.end());//進行去重for(int i=0;i<res.size()-1;i++){if(res[i]!=res[i+1]) result.push_back(res[i]);}result.push_back(res[res.size()-1]);return result;}
};

2、利用哈希集合加速

容器的選擇

1、map/multimap的幾個特點以及操作

元素包含兩部分(key,value),key和value可以是任意類型
根據元素的key自動對元素排序，因此根據元素的key可以進行很快定位
不能直接改變元素的key,可以通過[ ]直接存取元素值
map中不允許key相同的元素，multimap允許key相同的元素

操作	效果
map.c	產生空的map
c.size()	返回元素個數
count(key)	返回鍵值==key的元素個數
find(key)	返回鍵值==key 的第一個元素，找不到的話返回end
lower_bound(key)	返回鍵值>=key的第一個元素
upper_bound(key)	返回鍵值>key的第一個元素
equal_range(key)	返回鍵值==key的元素區間
c.insert(pos,e)	在pos位置為起點插入e的副本，并返回新元素的位置
c.erase(val)	移除所有值為val的元素，返回移除元素個數

2、set/multiset的幾個特點

set使用平衡二叉樹管理元素（紅黑樹）
set的每個元素值必須唯一，系統會自動將數據排序。他支持插入、刪除、查找等操作，所有的操作都在logN時間之內完成，效率比較高。
set和multiset的區別是：set插入的元素不能相同，而multiset可以相同 操作指令同map

代碼

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result;//構建nums1的哈希集合，自動去重，//set(集合)是將容器內所有元素都能更具其鍵值自動排序，set元素的鍵值就是實值。set不允許兩個元素有相同的鍵值unordered_set<int> nums1_res(nums1.begin(),nums1.end());for(int i=0;i<nums2.size();i++){//在哈希集合中尋找是否存在nums2[i]的元素，如果是的把這個元素放入result的哈希表中if(nums1_res.find(nums2[i])!=nums1_res.end())result.insert(nums2[i]);	        //在集合中插入元素（自動去重處理）	}return vector<int>(result.begin(),result.end()); }
};