哈希表就是为了快速查找的，查找效率极快
在涉及到查找的算法题中，可以考虑使用哈希思想
两数之和
class Solution {
public:
//解法一：暴力枚举：可以每次固定前面一个元素，再遍历这个元素后面的元素，看加起来有没有等于target的；另外，还有一种暴力枚举：就是从前面开始，固定一个元素，每次从这个元素前面找元素，看加起来有没有等于target的，这种解法是为了解法二的哈希解法
// vector<int> twoSum(vector<int>& nums, int target)
// {
// int n = nums.size();
// for(int i = 0; i < n; i++)
// {
// int tmp = target - nums[i];
// for(int j = 0; j < i; j++)
// {
// if(nums[j] == tmp)
// return {i, j};
// }
// }
// return {};
// }
//解法二：哈希解法：结合上述第二种暴力枚举，每次固定的元素和前面放入哈希表中的元素相加的值和target比较完之后，将这个固定元素及其下标入哈希，接着往后遍历
//为什么要这样，首先，可以一边比较查找一边构建哈希表；其次若是采用第一中暴力枚举，那么先构建哈希表（因为固定一个元素之后后面的元素不在哈希表无法查找）之后，可能查找时找到自己两次，比如target=8，固定的元素为4，此时在哈希表中查找，因为所有元素都在哈希表内，那么只有一个4时，就把这个固定的位置用来两次，还要特殊判断
//而第结合二种暴力枚举无妨，因为在固定的元素比较完之前，自己还没有入哈希表
vector<int> twoSum(vector<int>& nums, int target)
{
int n = nums.size();
unordered_map<int, int> hash;
for(int i = 0; i < n; i++)
{
int tmp = target - nums[i];
if(hash.count(tmp) != 0)//若是不等于-1，说明前面存在这个元素，直接返回
return {i, hash[tmp]};
//若是等于0，那么前面没有，入{nums[i], i}进hash
hash[nums[i]] = i;
}
return {};
}
};判断是否为字符重排
面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）
class Solution {
public:
//使用两个哈希表
// bool CheckPermutation(string s1, string s2) {
// vector<int> hash(26, 0);
// vector<int> hash2(26, 0);
// for(auto ch : s1)
// {
// hash[ch - 97]++;
// }
// for(auto ch : s2)
// {
// hash2[ch - 97]++;
// }
// for(int i = 0; i < 26; i++)
// {
// if(hash[i] != hash2[i])
// return false;
// }
// return true;
// }
//使用一个哈希表
bool CheckPermutation(string s1, string s2) {
if(s1.size() != s2.size())
return false;//长度不同一定不能重排
vector<int> hash(26, 0);
for(auto ch : s1)
{
hash[ch - 97]++;
}
for(auto ch : s2)
{
hash[ch - 97]--;
}
for(int i = 0; i < 26; i++)
{
if(hash[i] != 0)
return false;
}
return true;
}
};存在重复元素
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hash;
for(auto i : nums)
{
if(hash.count(i) == 1)
return true;
hash.insert(i);
}
return false;
}
};存在重复元素
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hash;
for(auto i : nums)
{
if(hash.count(i) == 1)
return true;
hash.insert(i);
}
return false;
}
};存在重复元素 II
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]) != 0)
{
if(abs(hash[nums[i]] - i) <= k)
return true;
}
hash[nums[i]] = i;//每次都更新成最新元素，因为找的两个下标应该是最近的
}
return false;
}
};字母异位词分组
这个题可以体现容器的强大
先判断字符串是否为异位词，若是则将它们放到同一个数组里面；这里可以用哈希表，key值为string，value为string[]，因为先将字符串排序了，那么互为异位词的字符串排序之后一定一样，那么就是key值一样，将对应的原词放入这个key值的value也就是数组中
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
unordered_map<string, vector<string>> hash;
for(auto i : strs)
{
string value = i;
sort(i.begin(), i.end());
hash[i].push_back(value);
}
for(auto i : hash)
{
ans.push_back(i.second);
}
return ans;
}
};