优选算法——哈希表
目录
1. 哈希表简介
2. 两数之和
3. 判定是否为字符重排
4. 存在重复元素
5. 字母异位词分组
1. 哈希表简介
2. 两数之和
题目链接：1. 两数之和 - 力扣（LeetCode）
题目展示：
题目分析：
大家来看上面的图，我们需要创建一个哈希表来存储数组下标以及对应位置的值，然后直接在哈希 表中查找每⼀个元素的target - nums[i] ，就能快速的找到「目标和的下标」。
• 因为哈希表中查找元素的时间复杂度是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++)
{
int x=target-nums[i];
if(hash.count(x))
{
return {hash[x],i};
}
hash[nums[i]]=i;
}
return {-1,-1};
}
};3. 判定是否为字符重排
题目链接：面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）
题目展示：
题目分析：
本题让我们作判断，那么我们的思路应该是看两个字符串中每个字符出现的次数，次数一样，就说明可以重排，否则就不行。那么既然想要统计出现次数，哈希表就要派上用场了。那么怎么利用哈希表来解决本题呢？
其实思路不难，我们只需要创建一个哈希表，把其中一个字符串放进去，对应位置++，然后再遍历另一个字符串，对应位置--，对应位置的值如果刚好都减为0，说明可以重排；否则就不可以重排。
代码实现：
class Solution {
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size()!=s2.size())
{
return false;
}
int hash[26]={0};
for(auto ch:s1)
{
hash[ch-'a']++;
}
for(auto ch:s2)
{
hash[ch-'a']--;
if(hash[ch-'a']<0)
{
return false;
}
}
return true;
}
};
4. 存在重复元素
题目链接：219. 存在重复元素 II - 力扣（LeetCode）
题目展示：
题目分析：
本题我们需要使用到哈希表，哈希表用来存储每个元素的下标信息。
代码实现：
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;
}
};大家可以看到，因为我们需要使用[ ]运算符，所以我们需要使用map来创建哈希表。
5. 字母异位词分组
题目链接：49. 字母异位词分组 - 力扣（LeetCode）
题目展示：
题目分析：本题我们需要充分地使用容器，大家来看下图。
我们创建这样的键值对，key为按照ASCII码值排好序的字符串，vaule为对应异位词，将它们放到哈希表中，最后我们需要将哈希表中的vaule提取出来就得到了我们想要的结果。
代码实现：
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;
}
};