优先算法——专题十：哈希表
哈希表就是为了快速查找的，查找效率极快
在涉及到查找的算法题中，可以考虑使用哈希思想
两数之和
1. 两数之和 - 力扣（LeetCode）
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}进hashhash[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;}
};存在重复元素
217. 存在重复元素 - 力扣（LeetCode）
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;}
};存在重复元素
217. 存在重复元素 - 力扣（LeetCode）
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;}
};字母异位词分组
49. 字母异位词分组 - 力扣（LeetCode）
这个题可以体现容器的强大
先判断字符串是否为异位词，若是则将它们放到同一个数组里面；这里可以用哈希表，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;}
};