知识铺垫——真的分得清哈希表吗
什么是哈希表
简单的来说，哈希表是一种表结构，我们可以直接根据给定的key值计算出目标位置。通常是采用数组实现了
与普通的列表不同的地方在于，普通列表仅能通过下标来获取目标位置的值，而哈希表可以根据给定的key计算得到目标位置的值。
在列表查找中，使用最广泛的二分查找算法，复杂度为O(log2n)，但其始终只能用于有序列表。普通无序列表只能采用遍历查找，复杂度为O(n)。而拥有较为理想的哈希函数实现的哈希表，对其任意元素的查找速度始终为常数级，即O(1)。
下面浅看一下官方对哈希表的描述吧。
C++里一般不直接使用这个库函数的，只是这种映射的思想比较重要，很多时候咱们数组模拟的哈希表其实也就是实现这个思想。
假如想手动实现核心的散列函数，这儿有两种比较常用的方式，可以作为积累，但是现在很少手动实现了吧
一、拉链法
二、开放寻址法
set 和 unordered_set
map 和 unordered_map
set 和 map的区别
第一题 1512. 好数对的数目
哈希表+组合数学
题目描述
解题报告
看到这种数据范围，啊，拿出可爱的暴力
题目让咱们求的是组合的情况，题目要求i < j这个条件我感觉可以忽视吧，只要有数列中有个相同的数字，就直接可以组合成数对了，大不了在书写的时候，写成i < j的模式。
让咱们求相同的数，两两组合的情况，比如现在有4个相同的数(样例二)，
两两组合的情况是C 4 2 C_{4}^2C 42= 4 * (4-1) / 2 = 6，符号样例二的输出结果
其他的相同数字两两组合的情况，也可以使用类似的方式计算出来的，在计算之前，咱们只是需要使用哈希表来统计数列中每个数出现的次数。
参考代码(C++版本)
解法一
class Solution { public: int numIdenticalPairs(vector<int>& nums) { int n = nums.size(); int ans = 0; for(int i = 0; i < n;i++) for(int j = i+1;j < n;j++) { if(nums[i] == nums[j] && i < j) ans ++; } return ans; } };
解法二：
class Solution { public: int numIdenticalPairs(vector<int>& nums) { //哈希表+组合数学 int cnt[110]; memset(cnt,0,sizeof(cnt)); int n = nums.size(); //统计给的数列中，每个数出现的情况 for(int i = 0; i < n;i++) cnt[nums[i]] ++; int ans = 0; for(int i = 0; i < 110;i++) //如果统计到某个数的个数至少有两个，那么就可以进行组合 //比如有三个1，组合的情况就是(3*2)/2 = 3 if(cnt[i] > 1) { ans += cnt[i]*(cnt[i]-1) / 2; } return ans; } };
第二题 2006. 差的绝对值为 K 的数对数目
题目描述
解题报告
题目的意思是去查找某个结果的时候，哈希表O(1)的时间复杂度或者二分O(logN)时间复杂度就可以多留意一下了。
对于本题而言，其实是让我们去统计满足要求的数字的个数，那咱们就可以使用一个哈希表，在将各个数值出现的次数统计出来的同时，按照题目要求的|nums[i] - nums[j]| = k，计算满足要求的数值的个数。
题目给的限制是|nums[i] - nums[j]| = k
将绝对值展开了，可以得到两个式子：
nums[i] = nums[j] + k
nums[i] = nums[j] - k
那咱们其实可以使用j作为下标从左到右遍历，统计是否有满足条件的i，倘若有就把其个数进行统计。
参考代码(C++版本)
解法一
class Solution { public: int countKDifference(vector<int>& nums, int k) { int ans = 0, n = nums.size(); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (abs(nums[i] - nums[j]) == k) ans ++; return ans; } };
解法二：
class Solution { public: int countKDifference(vector<int>& nums, int k) { unordered_map<int,int>h; int ans=0; int n = nums.size(); for(int j = 0;j < n;j++) { h[nums[j]] ++; ans += h[nums[j] + k]; ans += h[nums[j] - k]; } return ans; } };
第三题 1347. 制造字母异位词的最小步骤数
题目描述
解题报告
题目其实就是想要咱们求，将t字符串中的字母变成和s字符串中相同的字母(不论位置)，最少需要变换几个字符。
这个思路就很直接了吧，直接使用哈希表统计两个字符串中各个字母出现的情况，然后统计对于某个字符而言，t字符串中比s字符串中多的数量，这个多出来的部分，就是需要进行变换的数量。
参考代码(C++版本)
class Solution { public: int minSteps(string s, string t) { //直接将两个字符串哈希，然后统计不同的字符的个数就是答案 int n1 = s.size(); int cnts[26],cntt[26]; memset(cnts,0,sizeof(cnts)); memset(cntt,0,sizeof(cntt)); for(int i = 0; i < n1;i++) { cntt[t[i] - 'a'] ++; cnts[s[i] - 'a'] ++; } int ans = 0; for(int i = 0; i < 26;i++) if(cnts[i] < cntt[i]) ans += cntt[i] - cnts[i]; return ans; } };
第四题 面试题 10.02. 变位词组
排序+常规情况的变型
题目描述
解题报告
好家伙，数据范围都不放呢
这个题应该是属于小变型吧，之前咱们接触是映射字符，统计数量，比如将asdffdska存到哈希表unordered_map<char,int>中，其效果统计对应的字符的数量，字符a的数量是两个,字符d的数量是1个。
对于这个题而言了，是使用 unordered_map<string,vector<string>>统计相同字符串的不同形式，比如字符串aei的不同形式eia、aie等等。最本质的想法是一个的
参考代码(C++版本)
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { //其本质来说了，有点换汤不换药，因为之前统计的时候 //可以用哈希表统计某个相同的字母出现的次数 //这里了，统计某个相同的字符串 vector<vector<string>> ans; unordered_map<string,vector<string>> mp; int n = strs.size(); for(int i = 0; i < n;i++) { string str = strs[i]; //对取出的字符串进行排序 sort(str.begin(),str.end()); //把相同的字符串加入到哈希表中 mp[str].push_back(strs[i]); } //遍历这个哈希表统计结果，这里需要使用迭代器进行遍历了 //倘若手写是这种的 // unordered_map<string,vector<string>> :: iterator it; //倘若偷懒，是直接循环里放auto。遇事不决，我用auto... for(auto it = mp.begin(); it != mp.end(); it++) ans.push_back(it->second); return ans; } };
总结
总结了，哈希表和字符串是好朋友
