【算法系列】哈希表

哈希表总结

leetcode%E9%A2%98%E7%9B%AE-toc" style="margin-left:40px;">leetcode题目

一、两数之和

二、判定是否互为字符重排

三、存在重复元素

四、存在重复元素 II

五、字母异位词分组

六、在长度2N的数组中找出重复N次的元素

七、两个数组的交集

八、两个数组的交集 II

九、两句话中的不常见单词

哈希表总结

1.存储数据的容器

2.需要快速查找数据时，用哈希表

3.当题目中给定的字符串或者数组只包含小写字母或数据范围是0~100/1000等等时，可以用数组模拟哈希表

4.当数据范围是负数到正数时，不建议用数组模拟哈希表，因为还要加一个数转化之后进行映射，建议直接使用STL容器

leetcode%E9%A2%98%E7%9B%AE">leetcode题目

一、两数之和

1. 两数之和 - 力扣（LeetCode）https://leetcode.cn/problems/two-sum/1.题目解析

给定数组与target, 返回和为target的两个元素下标

2.算法分析

解法一: 暴力枚举

策略一: 先固定一个数，然后依次与该数之后的数相加

策略二: 先固定一个数，然后依次与该数之前的数相加

解法二: 使用哈希表优化

暴力解法之所以慢，以策略二为例, 是因为枚举到nums[i]时，要在这个位置之前都遍历一下，看哪个数字等于target-nums[i], 所以如果我们枚举到nums[i]时，前面的数字都被扔进了哈希表中，我们就可以以O(1)的时间复杂度找到结果~

注意：如果是用哈希表暴力枚举策略一，最好是倒着遍历~

3.算法代码

暴力枚举策略一:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i < nums.size(); i++){for(int j = i + 1; j < nums.size(); j++){if(nums[i] + nums[j] == target)return {i, j};  }}return {-1, -1};}
};

暴力枚举策略二:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 1; i < nums.size(); i++){for(int j = i - 1; j >= 0; j--){if(nums[i] + nums[j] == target)return {i, j};  }}return {-1, -1};}
};

哈希表优化策略一:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash; //<nums[i], i>for(int i = nums.size()-1; i >= 0; i--){int x = target - nums[i];if(hash.count(x)) return {hash[x], i};hash[nums[i]] = i;}return {-1, -1}; //照顾编译器} 
};

哈希表优化策略二:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash; //<nums[i], i>for(int i = 0; i < nums.size(); i++){int x = target - nums[i];if(hash.count(x)) return {hash[x], i};hash[nums[i]] = i;}return {-1, -1}; //照顾编译器} 
};

二、判定是否互为字符重排

面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）https://leetcode.cn/problems/check-permutation-lcci/1.题目解析

给定两个字符串，判断一个字符串是否能够通过重排变成另一个字符串

2.算法分析

如果s1能够重排形成s2, 那么s1每个字符出现的个数和s2对应字符出现的个数是相等的！于是可以使用哈希表，而题目中说字符串只有小写字母，因此用数组模拟哈希表即可。所以解法就是用两个哈希表，然后判断哈希表是否相等即可；

优化1: 只使用一个哈希表统计s1中字符个数，然后遍历第二个字符串，把对应字符在哈希表中的个数--，如果--之后是负数了，返回false即可

优化2: 两个字符串的长度不相等，直接返回false即可

3.算法代码

class Solution {
public:bool CheckPermutation(string s1, string s2){//优化if(s1.size() != s2.size()) return false;int hash[26] = {0};for(auto& e : s1)   hash[e - 'a']++;for(auto& e : s2){hash[e - 'a']--;if(hash[e - 'a'] < 0)return false;}return true;}
};

三、存在重复元素

217. 存在重复元素 - 力扣（LeetCode）https://leetcode.cn/problems/contains-duplicate/1.题目解析

数组中存在重复元素返回true, 不存在重复元素返回false

2.算法分析

使用哈希表解决问题~

3.算法代码

unordered_map:

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int, int> hash;for(auto& e : nums){hash[e]++;if(hash[e] > 1) return true;}return false;}
};

unordered_set:

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash;for(auto& e : nums){if(hash.count(e)) return true;elsehash.insert(e);}return false;}
};

四、存在重复元素 II

219. 存在重复元素 II - 力扣（LeetCode）https://leetcode.cn/problems/contains-duplicate-ii/1.题目解析

判断数组中是否存在两个相同的元素，并且下标的绝对值小于等于k

2.算法分析

从前向后遍历数组，同时将遍历过的元素和下标绑定扔进哈希表，遍历的同时判断是否满足题意即可

小细节：nums = [1 0 2 1 3 1 4], k =2, 当遍历到第2个1时，发现下标i-j=3>k, 不满足题意，此时将1和下标3绑定扔进哈希表覆盖之前的 <1, 0> 是完全可以的, 因为题目求的是 i-j <= k, 因此i和j越近越好，因此我们可以直接覆盖原先的值~

3.算法代码

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash; // <nums[i], i>for(int i = 0; i < nums.size(); i++){if(hash.count(nums[i]) && i-hash[nums[i]] <= k)return true;hash[nums[i]] = i;}return false;}
};

五、字母异位词分组

49. 字母异位词分组 - 力扣（LeetCode）https://leetcode.cn/problems/group-anagrams/description/1.题目解析

给一个字符串数组，将所有的字母异位词放到一组，返回一个二维数组

2.算法分析

1.判断两个字符串是否是字母异位词(可以用哈希表，但是代码不好写，我们选择直接排序, 排序结果一样，那就互为字母异位词)

2.将相同的字母异位词分组 --- 借助哈希表 <string, string[ ]>, 哈希表第一个位置存储排序后的字符串，第二个存储一个字符串数组；

3.算法代码

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;//1.将所有的字母异位词分组for(auto& s : strs){string tmp = s;sort(tmp.begin(), tmp.end());hash[tmp].push_back(s);}//2.提取结果vector<vector<string>> ret;for(auto& [x, y] : hash){ret.push_back(y);}return ret;}
};

六、在长度2N的数组中找出重复N次的元素

961. 在长度 2N 的数组中找出重复 N 次的元素 - 力扣（LeetCode）https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/description/1.题目解析

我们在深剖一下题意，本质就是只有1个数重复出现了，其他数都只出现了一次

2.算法分析

思路一: 遍历数组，将当前元素和出现次数丢进哈希表，当某个数出现次数 == n时，返回该数

思路二: 遍历数组，进循环先判断该数是否已经存在，存在就直接返回，不存在就将该数丢进哈希表

3.算法代码

思路一:

class Solution {  
public:  int repeatedNTimes(vector<int>& nums)  {  size_t n = nums.size() / 2;unordered_map<int, int> hash; // [x, count]  for(auto& e : nums)  {  hash[e]++;  if(hash[e] == n)   return e;  }  return -1;}  
};

思路二:

class Solution {  
public:  int repeatedNTimes(vector<int>& nums)  {  unordered_map<int, int> hash; // [x, count]  for(auto& e : nums)  {  if(hash[e] == 1) // 只需要检查是否已经存在（即重复了一次）  return e;  hash[e]++;  }  return -1;}  
};

七、两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-arrays/submissions/

1.题目解析

返回两个数组的交集（输出结果的每个元素要是唯一的）

2.算法分析

将两个数组元素扔进两个 unordered_set 哈希表进行去重，然后遍历其中一个哈希表，看该哈希表中的元素在另一个哈希表中是否存在，存在就插入到结果数组中！

3.算法代码

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;unordered_set<int> hash1;unordered_set<int> hash2;for(auto& e : nums1) //对nums1元素去重hash1.insert(e);for(auto& e : nums2) //对nums2元素去重hash2.insert(e);for(auto& e : hash1)if(hash2.count(e))ret.push_back(e);return ret;}
};

八、两个数组的交集 II

350. 两个数组的交集 II - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-arrays-ii/1.题目解析

返回两个数组的交集 (结果中可以有重复元素)

2.算法分析

定义一个哈希表 unordered_map，遍历第一个数组，将数组元素和出现的个数绑定扔进哈希表, 然后遍历第二个数组，元素在哈希表中出现，就插入到结果数组中，然后将该元素在哈希表中的个数--即可

3.算法代码

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> hash;for(auto& e : nums1)hash[e]++;vector<int> ret;for(auto& e : nums2){if(hash[e]){ret.push_back(e);hash[e]--;}}return ret;}
};

九、两句话中的不常见单词

884. 两句话中的不常见单词 - 力扣（LeetCode）https://leetcode.cn/problems/uncommon-words-from-two-sentences/description/

1.题目解析

返回两句话中互相在另一句话中没有出现的所有单词

2.算法分析

可以将两个字符串合在一起，提取出所有的单词同时扔进哈希表统计单词出现的次数，然后遍历一遍哈希表，出现次数为1的单词就是我们要的结果

3.算法代码

class Solution {
public:vector<string> uncommonFromSentences(string s1, string s2) {//1.将所有的单词提取出来vector<string> words;string tmp;string s = s1 + ' ' + s2;unordered_map<string, int> hash;for(size_t i = 0; i <= s.size(); i++){if(s[i] != ' ' && i != s.size())tmp += s[i];else{words.push_back(tmp);hash[tmp]++;tmp.clear();}}//2.从哈希表中提取结果vector<string> ret;for(auto [x, y] : hash)if(y == 1)ret.push_back(x);return ret;}
};

十、字符串中的第一个唯一字符

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）https://leetcode.cn/problems/first-unique-character-in-a-string/

1.题目解析

找字符串中第一个只出现一次的字符

2.算法分析

数组模拟哈希表，遍历字符串s，统计出每个字符出现的次数，然后再遍历一遍哈希表，找出出现次数为1的字符，返回下标

3.算法代码

class Solution {
public:int firstUniqChar(string s) {int hash[26] = {0};for(auto& e : s)hash[e-'a']++;for(int i = 0; i < s.size(); i++)if(hash[s[i]-'a'] == 1)return i;return -1;}
};