算法—哈希表题型讲解

一：两数之和

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) {if(s1.size() != s2.size())return false;vector<int> hash(26);for(auto& e1 : s1)hash[e1-'a']++;for(auto& e2 : s2)hash[e2-'a']--;for(auto& e : hash)if(e != 0)return false;return true;}
};

三：存在重复元素

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int, int> hash;   // 值与 相对应值的个数 的集合for(auto& e : nums){hash[e]++;if(hash[e] >= 2)return true;}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]) && ((i - hash[nums[i]]) <= k))return true;hash[nums[i]] = i;}return false;}
};

五：字母异位词分组

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash; // 字符串 与其相对应的 字母异位词 数组// 将所有的字母异位词分组for(auto& e : strs){string tmp = e;sort(tmp.begin(), tmp.end());hash[tmp].push_back(e);}// 提取结果vector<vector<string>> ret_vv_str;for(auto& [x, y] : hash){ret_vv_str.push_back(y);}return ret_vv_str;}
};