一、哈希表剖析
1、哈希表底层：通过对C++的学习，我们知道STL中哈希表底层是用的链地址法封装的开散列。
2、哈希表作用：存储数据的容器，插入、删除、搜索的时间复杂度都是O（1），无序。
3、什么时候使用哈希表：需要频繁查找数据的场景。
4、OJ中如何使用哈希表？？？
（1）STL中的容器（适用所有场景，比如字符串相关、数据映射下标）
（2）数组模拟简易哈希表（减小时间损耗，容器的封装有一定代价）—>大多以下两种情况适用
情况1：（char）涉及到字符串中的“字符” ，hash[26]可以映射所有的字母。
情况2：（int）数据范围较小的时候
二、两数之和
. - 力扣（LeetCode）
解法2代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int,int> hash; //数值和下标的映射关系
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)
{
//小优化
if(s1.size()!=s2.size()) return false;
//用哈希表
int hash[26]={0};
for(char&ch:s1) ++hash[ch-'a'];
//检测第二个数组
for(char&ch:s2) if(--hash[ch-'a']<0) return false;
return true;
}
};四、存在重复元素I
. - 力扣（LeetCode）
解法2代码：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hash; //有负数，所以必须用库里面的哈希表
for(auto&e:nums)
if(hash.count(e)) return true;
else hash.insert(e);
return false;
}
};五、存在重复元素II
. - 力扣（LeetCode）
解法1代码：
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int,size_t> hash;//数值和下标的映射
size_t n=nums.size();
for(size_t i=0;i<n;++i)
{
//如果哈希表中有这个数
if(hash.count(nums[i])&&i-hash[nums[i]]<=k) return true;
hash[nums[i]]=i;//存下标的映射
}
return false;
}
};解法2代码：
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
//滑动窗口解题，让set始终保存着k个元素，如果发现了区间内有重复元素，那么就可以返回true
unordered_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]);//不断将数字丢进去
if(i>=k) s.erase(nums[i-k]); //窗口超出区间了，就将最前面那个给删掉
}
return false;
}
};六、存在重复元素III(经典)
. - 力扣（LeetCode）
解法1代码：
class Solution {
public:
//绝对值尽量拆解掉
//滑动窗口解决问题（控制区间） 需要支持插入、查找、删除 尽可能有序 set
//k是下标的差值 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)
{
//在下标范围为 [max(0,i−k),i] 内找到值范围在 [u−t,u+t]的数。
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）分桶思路详细讲解
因为这个思路来源写得非常的详细，所以直接看就行，以往我们的分桶，更多的是针对整数的分桶，但是在该题中，扩展了存在负数的时候如何分桶，保证每个桶内的元素个数是一样的。这是一种非常巧妙的方法！！！要结合具体的实例去看！！
核心思路：保证每个桶内的绝对值相差小于t，k个桶。当我们遍历到这个数的时候，如果对应的桶的存在，就是true，如果相邻桶存在，看看差值是否符合要求。每个桶中只会有一个元素，因为有多的我们就会直接返回结果。
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); //找编号
//看看当前桶存不存在
if(hash.count(id)) return true;
//看看相邻桶在不在，如果在的话 就看看差值
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));//桶数多了，就去掉一个
hash[id]=u;//开新的桶
}
return false;
}
};七、字母异位词分组(经典)
. - 力扣（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个高频单词（经典）
. - 力扣（LeetCode）
解法1：map+vector+稳定排序+lambda优化
map的底层是红黑树，插入的时候map<string,int> 会按照字典序排好，而我们现在要按照出现次序去排序，同时对于出现次数相同的保证字典序在前面，所以我们其中之一的策略就是vector+sort ,但是sort底层是快排，并不具备稳定性，但是库里面有一个stable_sort是稳定的排序
class Solution {
public:
typedef pair<string,int> PSI;
vector<string> topKFrequent(vector<string>& words, int k)
{
map<string,int> countmap;//计数
for(auto&s:words) ++countmap[s];
//此时已经按照字典序排好了，将其拷贝到vector中
vector<PSI> nums(countmap.begin(),countmap.end());
//要用一个稳定的排序 我们排序的是比较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+调整比较逻辑+lambda优化
class Solution {
public:
typedef pair<string,int> PSI;
vector<string> topKFrequent(vector<string>& words, int k)
{
unordered_map<string,int> countmap;//计数
for(auto&s:words) ++countmap[s];
//此时已经按照字典序排好了，将其拷贝到vector中
vector<PSI> nums(countmap.begin(),countmap.end());
//要用一个稳定的排序 我们排序的是比较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//要注意仿函数要+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;//计数
for(auto&s:words) ++countmap[s];
//丢到优先级队列里
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]=().first;
heap.pop();
}
return ret;
}
};解法4：unordered_map+multiset+compare类
class Solution {
public:
typedef pair<string,int> PSI;
struct compare//要注意仿函数要+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;//计数
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实现了字典序的排序。而底层的multimap封装中对于相同的键值是优先插入到其右侧。
class Solution {
public:
struct compare//要注意仿函数要+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;//计数
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;
}
};
