目录
哈希表总结
1.存储数据的容器
2.需要快速查找数据时，用哈希表
3.当题目中给定的字符串或者数组只包含小写字母或数据范围是0~100/1000等等时，可以用数组模拟哈希表
4.当数据范围是负数到正数时，不建议用数组模拟哈希表，因为还要加一个数转化之后进行映射，建议直接使用STL容器
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;
else
hash.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次的元素
我们在深剖一下题意，本质就是只有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;
}
};九、两句话中的不常见单词
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;
}
};
