文章目录
本文总结的是关于哈希表常见的算法
哈希表其实就是一个存储数据的容器，所以其实它本身的算法难度并不高，只是利用哈希表可以对于一些场景进行优化
两数之和
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};
}
};
判断是否互为字符重排
class Solution
{
public:
bool CheckPermutation(string s1, string s2)
{
int hash1[26] = {
0};
for(auto e : s1)
hash1[e - 'a']++;
for(auto e : s2)
hash1[e - 'a']--;
for(int i = 0; i < 26; i++)
if(hash1[i])
return false;
return true;
}
};
存在重复元素
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_map<int, int> dict;
for(auto& e : nums)
dict[e]++;
for(auto& e : nums)
if(dict[e] != 1)
return true;
return false;
}
};
其实是可以优化的，不需要看出现了几次，这个题只关心有没有的问题，因此使用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;
}
};
存在重复元素
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]) && abs(hash[nums[i]] - i) <= k)
{
return true;
}
else
{
hash[nums[i]] = i;
}
}
return false;
}
};
字母异位词分组
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>> res;
for(auto& [x, y] : hash)
{
res.push_back(y);
}
return res;
}
};
这里主要是说明，哈希表中是可以存储其他内容的，同时也体现出泛型编程的强大之处
