【基础算法总结】哈希表/set/map篇
目录
一，哈希表简介
哈希思想是算法中一个十分重要的思想，体现的是一种映射关系，而哈希表就是基于哈希思想实现的存储数据的容器。哈希表的作用是快速查找某个元素，时间复杂度为O(1)，时间复杂度为O(n)。
使用哈希一般有两种方式：
(1)STL中的 unordered系列容器。
(2)用数组模拟简易哈希表。这种情况一般用于处理字符串中的"字符"或是当数据范围很小的时候使用。
下面将通过若干道题目进一步体会哈希表的使用。
二，算法原理和代码实现
1.两数之和
算法原理：
(1) 如果我们可以事先将数组内的元素和下标绑定在⼀起存⼊哈希表中，然后直接在哈希表中查找每⼀个元素的 target - nums[i] ，就能快速的找到⽬标和的下标。
(2) 这⾥有⼀个⼩技巧，我们可以不⽤将元素全部放⼊到哈希表之后，再来⼆次遍历(因为要处理元素相同的情况)。⽽是在将元素放⼊到哈希表中的同时，直接来检查表中是否已经存在当前元素所对应的⽬标元素(即 target - nums[i] )。如果它存在，那我们已经找到了对应解，并⽴即将其返回。⽆需将元素全部放⼊哈希表中，提⾼效率。
(3) 因为哈希表中查找元素的时间复杂度是 O(1) ，遍历⼀遍数组的时间复杂度为 O(N) ，因此可以将时间复杂度降到 O(N)。
代码实现：
class Solution { public: vector<int>twoSum(vector<int>& nums,int target){ unordered_map<int,int> hash;// 存元素和对应的下标for(int i =0; i < nums.size(); i++){// 检查在该元素之前是否存在一个数等于target-nums[i]int x = target - nums[i];if(hash.count(x))return{hash[x], i}; hash[nums[i]]= i;// 不存在就插入}return{-1,-1};}};349.两个数组的交集
算法原理：
解法1：使用哈希表。
定义两个哈希表 hash1 和 hash2 ，把两个数组都扔进哈希表中进行去重，遍历 hash1 中的每个元素，在 hash2 中查找是否存在，若存在就是交集。把交集存入数组里即可。
代码实现：
class Solution { public: vector<int>intersection(vector<int>& nums1, vector<int>& nums2){// 去重 unordered_set<int>s1(nums1.begin(), nums1.end()); unordered_set<int>s2(nums2.begin(), nums2.end());// 遍历s1,在s2中查找是否存在，若存在就是交集 vector<int> ret;for(auto x : s1)if(s2.find(x)!= s2.end()) ret.push_back(x);return ret;}};解法2：使用 set 排序+去重。
这种解法不仅能找出交集，也能找到差集。
把两个数组都扔进 set 容器达到排序+去重的效果，再依次比较两个 set 里的元素，谁小谁++，相等时再同时++，此时相等的元素就是交集，较小的元素就是差集，直到其中一个 set 走完了，另一个 set 剩下的元素也是差集。
代码实现：
class Solution { public: vector<int>intersection(vector<int>& nums1, vector<int>& nums2){// 排序+去重 set<int>s1(nums1.begin(), nums1.end()); set<int>s2(nums2.begin(), nums2.end());// 依次比较，谁小谁++，相等的就是交集，再同时++auto it1 = s1.begin(), it2 = s2.begin(); vector<int> ret;while(it1 != s1.end()&& it2 != s2.end()){if(*it1 <*it2)++it1;elseif(*it1 >*it2)++it2;else ret.push_back(*it1),++it1,++it2;}return ret;}};面试题01.02.判断是否互为字符重排
算法原理：
(1) 当两个字符串的⻓度不相等的时候，是不可能构成互相重排的，直接返回 false。
(2) 如果两个字符串能够构成互相重排，那么每个字符串中各个字符出现的次数⼀定是相同的。因此，我们可以分别统计出这两个字符串中各个字符出现的次数，然后逐个⽐较是否相等即可。所以可以选择哈希表来统计字符串中字符出现的次数。
代码实现：
class Solution { public: bool CheckPermutation(string s1, string s2){// 长度不相等，直接返回falseif(s1.size()!= s2.size())return false;int hash1[26]={0}, hash2[26]={0};// 先统计s1和s2中每个字符出现得到次数for(auto ch : s1) hash1[ch -'a']++;for(auto ch : s2) hash2[ch -'a']++;// 再比较两个哈希表中每个字符出现的次数是否相同for(char ch ='a'; ch <='z'; ch++)if(hash1[ch -'a']!= hash2[ch -'a'])return false;return true;}};优化：只使用一个哈希表。
用一个哈希表先统计s1中每个字符出现的个数，再遍历s2时把s2中出现的字符在哈希表中-1。如果构成重排列，则最后哈希表中的个数都为0，否则不构成。
代码实现：
class Solution { public: bool CheckPermutation(string s1, string s2){// 长度不相等，直接返回falseif(s1.size()!= s2.size())return false;int hash[26]={0};// 统计s1中字符出现的次数for(auto ch : s1) hash[ch -'a']++;// 再遍历s2,出现的字符-1for(auto ch : s2) hash[ch -'a']--;// 最后检查hash里是否都为0for(int i =0; i <26; i++)if(hash[i]!=0)return false;return true;}};217.存在重复元素
算法原理：
这道题和第一题的做法基本类似。
分析⼀下题⽬，出现⾄少两次的意思就是数组中存在着重复的元素，因此我们可以⽆需统计元素出现的数⽬。仅需在遍历数组的过程中，检查当前元素是否在之前已经出现过即可。
因此我们可以利⽤哈希表，仅需存储数组内的元素。在遍历数组的时候，⼀边检查哈希表中是否已经出现过当前元素，⼀边将元素加⼊到哈希表中。
代码实现：
class Solution { public: bool containsDuplicate(vector<int>& nums){ unordered_set<int> hash;for(auto x : nums)if(hash.count(x))return true;else hash.insert(x);return false;}};219.存在重复元素II
算法原理：
这道题和上一题基本一样，只不过除了要两个元素相等之外，还需要判断相等元素的下标差的绝对值是否小于等于k。所以本题的哈希表要把元素值和对应下标绑定。
细节问题：
如果数组内存在⼤量的重复元素，⽽我们判断下标差的绝对值不符合要求时，在插入相同元素的下标，会覆盖掉原来的下标，那结果还正确吗，怎么处理？
结果依然是正确的，可以大胆的覆盖掉!
原因：
我们按照下标从⼩到⼤的顺序遍历数组，当遇到两个元素相同，并且⽐较它们的下标时，这两个下标⼀定是距离最近的，因为：
(1) 如果当前判断符合条件直接返回 true ，⽆需继续往后查找。
(2) 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配(因为下标在逐渐变大)，那么我们可以大胆舍去前⼀个存储的下标，转⽽将其换成新的下标，继续匹配。
代码实现：
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums,int k){ unordered_map<int,int> hash;// 绑定元素和下标for(int i =0; i < nums.size(); i++){if(hash.count(nums[i])){if(abs(hash[nums[i]]- i)<= k)return true;} hash[nums[i]]= i;}return false;}};692.前k个高频单词
算法原理：
解法：使用 map + 稳定排序函数。
先用map统计出每个单词出现的次数，map中是按照单词的字典序排序的，所以还需要用排序函数对次数进行排降序，最后提取出前 k 个出现最多的字符串。
魔鬼细节问题：
对次数再排序时有以下几个注意点：
(1)排序函数一定要使用稳定排序!算法库中的 sort 是不稳定的，但是 stable_sort 是稳定的。
因为如果使用不稳定的排序，则出现次数相同的字符串顺序又会被打乱(map 中已经是按单词的字典序排序的)，不符合题意。
(2) 使用排序函数之前要把 map 中的元素先导入 vector 中，再传递 vector 的迭代器给 stable_sort 。
因为stable_sort 只能传递随机迭代器，而 map 的迭代器是双向迭代器，vector 的迭代器是随机迭代器。
(3) stable_sort 的第三个参数：一个可调用的比较函数和函数对象。
代码实现：
class Solution {structkvcmp{ bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2){return kv1.second > kv2.second;}}; public: vector<string>topKFrequent(vector<string>& words,int k){// 统计每个字符串出现的次数 map<string,int> mapCnt;for(auto& s : words) mapCnt[s]++; vector<pair<string,int>>v(mapCnt.begin(), mapCnt.end());// 要用稳定排序对字符串出现的次数排降序stable_sort(v.begin(), v.end(),kvcmp());// 提取出前 k 个出现次数最多的单词 vector<string> ret;for(int i =0; i < k; i++) ret.push_back(v[i].first);return ret;}};45.字母异位词分组
算法原理：
这道题要解决两个问题：
(1) 判断两个字符串是否是字母异位词。
我们可以使用上面题目中的做法用哈希表统计字符出现的个数再进行判断。这里用另一种更简洁的方法，排序，但是时间复杂度更高。把每个字符串按字典序进行排序，若是字母异位词，则排完序后字符串相等，否则不相等。
(2) 如何把字母异位词分组。
我们可以这样定义哈希表，把 key 定义为 string，把 value 定义为字符串数组 vector< string >。
把每个字符串排序后再去哈希表中查找，如果存在，就把它绑定到对应的字符串数组中。
代码实现：
class Solution { public: vector<vector<string>>groupAnagrams(vector<string>& strs){ unordered_map<string, vector<string>> hash;// 把所有的字母异位词分组for(auto& s : strs){ string tmp = s;sort(tmp.begin(), tmp.end()); hash[tmp].push_back(s);}// 提取结果 vector<vector<string>> ret;for(auto&[x, y]: hash) ret.push_back(y);return ret;}};三，算法总结
通过上面的若干道题目可以发现，哈希容器/map/set是非常强大的，能够快速的查找数据是否存在，统计数据个数，去重，排序。
