一、哈希表剖析

1、哈希表底層：通過對C++的學(xué)習(xí)，我們知道STL中哈希表底層是用的鏈地址法封裝的開散列。

2、哈希表作用：存儲數(shù)據(jù)的容器，插入、刪除、搜索的時間復(fù)雜度都是O（1），無序。

3、什么時候使用哈希表：需要頻繁查找數(shù)據(jù)的場景。

4、OJ中如何使用哈希表？？？

（1）STL中的容器（適用所有場景，比如字符串相關(guān)、數(shù)據(jù)映射下標(biāo)）

（2）數(shù)組模擬簡易哈希表（減小時間損耗，容器的封裝有一定代價）—>大多以下兩種情況適用

情況1：（char）涉及到字符串中的“字符” ，hash[26]可以映射所有的字母。

情況2：（int）數(shù)據(jù)范圍較小的時候

二、兩數(shù)之和

. - 力扣（LeetCode）

解法2代碼：?

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target){unordered_map<int,int> hash; //數(shù)值和下標(biāo)的映射關(guān)系int n=nums.size();for(int i=0;i<n;++i){int x=target-nums[i];if(hash.count(x)) return {hash[x],i};hash[nums[i]]=i;}return {-1,-1};}
};

?三、判定是否互為字符重排

. - 力扣（LeetCode）

?解法2代碼：

class Solution {
public:bool CheckPermutation(string s1, string s2) {//小優(yōu)化if(s1.size()!=s2.size()) return false;//用哈希表int hash[26]={0};for(char&ch:s1) ++hash[ch-'a'];//檢測第二個數(shù)組for(char&ch:s2)  if(--hash[ch-'a']<0)  return false;return true;}
};

四、存在重復(fù)元素I

. - 力扣（LeetCode）

解法2代碼：

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash; //有負(fù)數(shù)，所以必須用庫里面的哈希表for(auto&e:nums) if(hash.count(e)) return true;else hash.insert(e);return false;}
};

?五、存在重復(fù)元素II

. - 力扣（LeetCode）

解法1代碼：

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,size_t> hash;//數(shù)值和下標(biāo)的映射size_t n=nums.size();for(size_t i=0;i<n;++i){//如果哈希表中有這個數(shù)if(hash.count(nums[i])&&i-hash[nums[i]]<=k) return true;hash[nums[i]]=i;//存下標(biāo)的映射}return false;}
};

解法2代碼：

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {//滑動窗口解題，讓set始終保存著k個元素，如果發(fā)現(xiàn)了區(qū)間內(nèi)有重復(fù)元素，那么就可以返回trueunordered_set<int> s;size_t n=nums.size();for(size_t i=0;i<n;++i){if(s.count(nums[i])) return true;s.emplace(nums[i]);//不斷將數(shù)字丟進(jìn)去if(i>=k) s.erase(nums[i-k]); //窗口超出區(qū)間了，就將最前面那個給刪掉}return false;}
};

六、存在重復(fù)元素III(經(jīng)典)

. - 力扣（LeetCode）

?解法1代碼：

class Solution {
public://絕對值盡量拆解掉//滑動窗口解決問題（控制區(qū)間）  需要支持插入、查找、刪除  盡可能有序 set//k是下標(biāo)的差值  t是元素的差值bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {//lower_bound 利用二分找到第一個>=num的迭代器 降序就是<=//upper_bound 利用二分找到第一個>num的迭代器  降序就是<set<long> s;//需要一個有序集合for(size_t i=0;i<nums.size();++i){ //在下標(biāo)范圍為 [max(0,i?k),i] 內(nèi)找到值范圍在 [u?t,u+t]的數(shù)。set<long>::iterator it=s.lower_bound((long)nums[i]-t);if(it!=s.end()&&*it<=(long)nums[i]+t) return true;s.insert(nums[i]);if(i>=k)  s.erase(nums[i - k]);}return false;}
};

?思路2：分桶（非常精巧的思路）

思路來源：. - 力扣（LeetCode）分桶思路詳細(xì)講解

? ? ?因為這個思路來源寫得非常的詳細(xì)，所以直接看就行，以往我們的分桶，更多的是針對整數(shù)的分桶，但是在該題中，擴(kuò)展了存在負(fù)數(shù)的時候如何分桶，保證每個桶內(nèi)的元素個數(shù)是一樣的。這是一種非常巧妙的方法！！！要結(jié)合具體的實例去看！！

核心思路：保證每個桶內(nèi)的絕對值相差小于t，k個桶。當(dāng)我們遍歷到這個數(shù)的時候，如果對應(yīng)的桶的存在，就是true，如果相鄰?fù)按嬖?#xff0c;看看差值是否符合要求。每個桶中只會有一個元素，因為有多的我們就會直接返回結(jié)果。

class Solution {
public:int getid(long u,long t){return u>=0?u/(t+1):(u+1)/(t+1)-1;}bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {//桶排序   size_t n=nums.size();//分成k個桶  每個桶的大小是t+1 (0,1,2,3) ->保證一個桶里面是符合的unordered_map<int,int> hash;  //第一個是存id  第二個是存元素for(size_t i=0;i<n;++i){long u=nums[i];int id= getid(u,t); //找編號//看看當(dāng)前桶存不存在if(hash.count(id)) return true;//看看相鄰?fù)霸诓辉?#xff0c;如果在的話 就看看差值if(  hash.count(id-1)&&u-hash[id-1]<=t||hash.count(id+1)&&hash[id+1]-u<=t) return true;if(i>=k) hash.erase(getid(nums[i-k],t));//桶數(shù)多了，就去掉一個hash[id]=u;//開新的桶}return false;}
};

七、字母異位詞分組(經(jīng)典)

. - 力扣（LeetCode）

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {//字母異位詞->排序后都是相同的unordered_map<string,vector<string>> hash; //將異位詞綁定起來for(auto&s:strs){string temp=s;sort(temp.begin(),temp.end());hash[temp].emplace_back(s);}//提取出來vector<vector<string>> ret;for(auto&[x,y]:hash)  ret.emplace_back(y); //取哈希表中鍵值對的方法C++14支持//for(auto&kv:hash)  ret.push_back(kv.second);return ret;}
};

八、前K個高頻單詞（經(jīng)典）

?. - 力扣（LeetCode）

解法1：map+vector+穩(wěn)定排序+lambda優(yōu)化
? ? ? ? ? map的底層是紅黑樹，插入的時候map<string,int> 會按照字典序排好，而我們現(xiàn)在要按照出現(xiàn)次序去排序，同時對于出現(xiàn)次數(shù)相同的保證字典序在前面，所以我們其中之一的策略就是vector+sort ,但是sort底層是快排，并不具備穩(wěn)定性，但是庫里面有一個stable_sort是穩(wěn)定的排序

class Solution {
public:typedef pair<string,int> PSI;vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countmap;//計數(shù)for(auto&s:words) ++countmap[s];//此時已經(jīng)按照字典序排好了，將其拷貝到vector中vector<PSI> nums(countmap.begin(),countmap.end());//要用一個穩(wěn)定的排序 我們排序的是比較value，所以要修改比較邏輯stable_sort(nums.begin(),nums.end(),[](const PSI&kv1,const PSI&kv2) {return kv1.second>kv2.second;});vector<string> ret(k);for(int i=0;i<k;++i)  ret[i]=nums[i].first;return ret;}
};

解法2：unordered_map+vector+sort+調(diào)整比較邏輯+lambda優(yōu)化?

class Solution {
public:typedef pair<string,int> PSI;vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> countmap;//計數(shù)for(auto&s:words) ++countmap[s];//此時已經(jīng)按照字典序排好了，將其拷貝到vector中vector<PSI> nums(countmap.begin(),countmap.end());//要用一個穩(wěn)定的排序 我們排序的是比較value，所以要修改比較邏輯sort(nums.begin(),nums.end(),[](const PSI&kv1,const PSI&kv2){ return kv1.second>kv2.second||(kv1.second==kv2.second&&kv1.first<kv2.first);});vector<string> ret(k);for(int i=0;i<k;++i)  ret[i]=nums[i].first;return ret;}
};

上面兩種解法都是借助vector容器+sort去解決的。

?解法3：unordered_map+priority_queue+compare類

class Solution {
public:typedef pair<string,int> PSI;struct compare//要注意仿函數(shù)要+const修飾，否則可能編譯不過{bool operator()(const PSI&kv1,const PSI&kv2) const{if(kv1.second==kv2.second) return kv1.first<kv2.first;return kv1.second>kv2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> countmap;//計數(shù)for(auto&s:words) ++countmap[s];//丟到優(yōu)先級隊列里priority_queue<PSI,vector<PSI>,compare> heap;for (auto& it : countmap) {heap.push(it);if (heap.size() > k) heap.pop();}vector<string> ret(k);for(int i=k-1;i>=0;--i) {ret[i]=heap.top().first;heap.pop();}return ret;}
};

?解法4：unordered_map+multiset+compare類

class Solution {
public:typedef pair<string,int> PSI;struct compare//要注意仿函數(shù)要+const修飾，否則可能編譯不過{bool operator()(const PSI&kv1,const PSI&kv2) const{return kv1.second>kv2.second||(kv1.second==kv2.second&&kv1.first<kv2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> countmap;//計數(shù)for(auto&s:words) ++countmap[s];multiset<PSI,compare> sortmap(countmap.begin(),countmap.end());vector<string> ret(k);multiset<PSI,compare>::iterator it=sortmap.begin();size_t i=0;while(k--) {ret[i++]=it->first;++it;}return ret;}
};

?解法5：map+multimap+compare類（能過 但這是巧合）

? ? ? ?這題能過的原因是map實現(xiàn)了字典序的排序。而底層的multimap封裝中對于相同的鍵值是優(yōu)先插入到其右側(cè)。

class Solution {
public:struct compare//要注意仿函數(shù)要+const修飾，否則可能編譯不過{bool operator()(const int&k1,const int&k2) const{return k1>k2;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countmap;//計數(shù)for(auto&s:words) ++countmap[s];multimap<int,string,compare> sortmap;for(auto &kv:countmap) sortmap.insert(make_pair(kv.second,kv.first));vector<string> ret(k);auto it=sortmap.begin();size_t i=0;while(k--) {ret[i++]=it->second;++it;}return ret;}
};