算法：常見的哈希表算法

文章目錄

兩數之和
判斷是否互為字符重排
存在重復元素
存在重復元素
字母異位詞分組

本文總結的是關于哈希表常見的算法

哈希表其實就是一個存儲數據的容器，所以其實它本身的算法難度并不高，只是利用哈希表可以對于一些場景進行優化

兩數之和

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;}
};