哈希表简介：
通过以下几个问题来解释~
1、哈希表是什么？
存储数据的容器。
2、有什么用？
“快速”查找某个元素。时间复杂度O(1) 空间复杂度O(N)
3、什么时候使用哈希表
频繁的查找某个数时。
4、怎么用哈希表
第一种就是直接使用哈希表的容器。
第二种利用数组实现（在数据范围很小的情况下，比如字符）
下面就开始实战！
第一题、1. 两数之和
解析：
按正常算法时间复杂度为O(N^2)，利用哈希就是以空间换时间的算法。时间和空间的复杂度都是O(N)。
将数组中的数存储进入哈希，然后用count函数去寻找，如果存在，直接返回结果。
原码：
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 {i,hash[x]};
//插入哈希表
hash[nums[i]] = i;
}
//照顾编译器
return {-1,-1};
}
};第二题：判定是否互为字符重排
解析：
本题也是用空间换时间复杂度的算法。
该题可以不用库里的容器，自己用数组模拟哈希，因为本题最多只有26个字符，数据范围较小。
然后遍历第一个字符串，进行模拟++，再去遍历第二个字符串，看字符出现的次数是否一致。
原码：
class Solution {
public:
bool CheckPermutation(string s1, string s2) {
//先判断字符串不相等特殊情况
if(s1.size() != s2.size()) return false;
//直接模拟哈希表
int hash[26] = {0};
//先统计第一个字符串信息
for(int i = 0;i<s1.size();i++)
{
hash[s1[i] - 'a']++;
}
//扫描第二个字符串，看看是否能重排
for(int i = 0;i<s2.size();i++)
{
hash[s2[i] - 'a']--;
if(hash[s2[i] - 'a'] < 0) return false;
}
return true;
}
};第三题、49. 字母异位词分组
题目描述：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解析：
本道题就体现了哈希表的强大之处，我们可以将哈希表存储为： unordered_map<string,vector<string>> hash;//<first,second>
我们先将每个字符串进行排序，然后以该字符串排好序后为基准值，进行存储。文章来源：https://www.toymoban.com/news/detail-836151.html
最后我们再将second存储在vector数组中即可~文章来源地址https://www.toymoban.com/news/detail-836151.html
原码：
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> hash;//<first,second>
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)//只需要存储second，也就是y
{
ret.push_back(y);
}
return ret;
}
};到了这里，关于算法讲解之哈希表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
