1. 哈希表是什么?
本质上来说哈希表只是一个存储数据的容器
2. 为什么用哈希表?
哈希表查找元素的速度很快, O(1)级别; 但是代价是O(n)的空间复杂度, 属于空间换时间
3. 什么时候用哈希表?
频繁的查找某个数的时候, 但是并不是所有的查找都用哈希表, 对顺序排列的元素用二分搜索O(logN)
4. 怎么用哈希表?
1. 一般常用的高级语言的库都会提供哈希表, 直接使用即可
2. 用数组模拟一个简易的哈希表, 这样会比容器更快
1. 比如字符串里的字符, 如果全是大写/小写英文字母, int hash[26]; hash[c-'A']即为c字符的个数, 键值对的形式是: <index, hash[index]> ,value可以是字符出现的次数, 索引等等
2. 数据范围很小的时候,整数的范围在 [1~10^x], x在[3,7] , 但是出现负数就不推荐使用数组, 因为需要加一个偏移量, 比较麻烦.
我们同样可以用哈希函数去模拟哈希表, 但是可能没必要
题目1: 两数之和
1. 暴力解法
暴力解法有两种思路:
第一种是从 i=0 开始, j = [i+1 , nums.size()-1] 依次遍历剩下的元素查找是否有和为target的元素.
第二种也是从i=0开始, 但是j从i开始向前寻找, 也是遍历了所有的元素, 时间复杂度没有任何区别.
第二种:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i < nums.size(); i++){for(int j = i; j > 0;j--){if(nums[i] + nums[j-1] == target)return {i,j-1};}}return {0,0};}
};2. 哈希表
哈希的思路是从第二种暴力解法得来的, 哈希表里存储<数值, index>.
i 也是从 0 开始向后遍历, 查找另一个元素实际可以转化成查找hash表里是否有 target-nums[i] 这个key, 如果有返回{i, hash[target-nums[i]] } 即可. 没有就在hash里添加这个键值对, 实质是把寻找的过程从 O(n) 降为了 O(1)
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hash;int i = 0;while(i < nums.size()){int num = target-nums[i];if(hash.find(num) != hash.end())return {i, hash[num]};hash[nums[i]] = i;i++; }return {0,0};}
};从第一种暴力解法延伸而来的哈希也可以, 但是由于在第一遍寻找时就把所有元素加入到了哈希表, 因此如果一个值 2*nums[i] == target, 那它会查找到自身返回{i,i}因此需要特殊处理这种情况
题目2: 判断是否互为字符重排
思路: 如果s1重排后能得到s2, 那么s1中每个字符出现的个数一定等于s2中对应字符出现的个数
写法1: 两个哈希表统计s1和s2字符个数, 然后比较即可:
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.length() != s2.length())return false;unordered_map<char,int> hash1;unordered_map<char,int> hash2;for(int i = 0; i < s1.length();i++){hash1[s1[i]]++;hash2[s2[i]]++;}for(const auto& e : hash1){if(hash2[e.first] != e.second)return false;}return true;}
};写法2: 只使用一个哈希表统计 s1 的字符出现次数, 再遍历 s2 依次对hash表元素次数减一, 如果可以重排, 最终哈希表所有元素的值都应该是0, 如果出现负值, 则无法重排.
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.length() != s2.length())return false;int hash[26] = {0};for(int i = 0; i < s1.length();i++)hash[s1[i]-'a']++;for(int i = 0; i < s2.length();i++){if(--hash[s2[i]-'a'] < 0)return false; }return true;}
};注意: 两种写法都需要对长度不相等的字符串特殊处理, 长度不相等一定无法重排
题目3: 存在重复元素 I
和两数之和思路类似, 遍历一次向前查找hash里是否有数存在, 不存在就存入哈希表, 继续遍历:
class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash;for(int i = 0; i < nums.size(); ++i){if(hash.count(nums[i]))return true;hash.insert(nums[i]);}return false;}
};题目4: 存在重复元素 I I
这题和存在重复元素I 类似, 也是遍历一次向前查找哈希表即可, 但是每次寻找还需要比较下标之差gap和k的关系, 因此需要用unordered_map存储下标.
注意: 有一个细节需要注意, 因为unordered_map相同的key只能存在一个, 所以下一次遇到相同元素如果不满足gap <= k, 要覆盖吗?
要, 因为我们是从前向后遍历, gap = j - i 的值会随 j 的增大而增大, 所以如果本次gap > k, 随着 j 增大gap会越来越大, 不可能符合要求. 所以要覆盖掉原来的 i , 这样使之后gap的值变得更小, 更容易满足要求.
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(i - hash[nums[i]] <=k)return true;}hash[nums[i]] = i;}return false;}
};题目5: 字⺟异位词分组
此题是题目2的升级版, 需要把字母异位词全组合到一起, 这题充分体现出hash容器和泛型编程的好处.
对于所有的字母异位词, 它们按照 某种规则排序后的词 字母顺序一定是一样的, 因此利用一个unordered_map<string, vector<string>>, 将一类字母异位词全部映射到一个vector里即可:
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;vector<vector<string>> ret;for(const auto& s : strs){string tmp = s;sort(tmp.begin(),tmp.end());hash[tmp].push_back(s);}for(auto & pair: hash)ret.push_back(pair.second);return ret;}
};暂时结束
