目录
1前言
2.例题
2.1两数之和
2.2判断是否互为字符重排
2.3存在重复元素1
2.4存在重复元素2
2.5字母异位词分组
1前言
哈希表主要是适合于快速查找某个元素（O(1)）
当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n)
一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。
最简单的比如数组模拟字符存储，只要开26个char的数组即可。
用数组模拟速度比用容器哈希快。但是有局限性（主要是针对数据范围小的时候）
2.例题
2.1两数之和
1. 两数之和 - 力扣（LeetCode）
利用哈希表，存储当前位置数字前的所有数字。
这样可以直接查询需要的数字。
class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {int n=nums.size();unordered_map<int,int>hash1;for(int i=0;i<n;i++){if(hash1.count(target-nums[i])){return {hash1[target-nums[i]],i};}hash1[nums[i]]=i;}return {};} };2.2判断是否互为字符重排
面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）
思路1
利用两个哈希表，一个存s1中字符出现个数，一个存s2中字符出现个数
然后比较两个哈希表即可
注意，这题是字符，所以直接用数组模拟即可。
class Solution { public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;int hash1[26]={0};int hash2[26]={0};//统计s1for(auto a:s1){hash1[a-97]++;}//统计s2for(auto a:s2){hash2[a-97]++;}//比较for(int i=0;i<26;i++){if(hash1[i]!=hash2[i])return false;}return true;} };思路2
区别不大。只用1个哈希表。遍历s2的时候，同步更新
class Solution { public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;int hash1[26]={0};for(auto a:s1){hash1[a-97]++;}for(auto a:s2){hash1[a-97]--;if(hash1[a-97]<0)return false;} //比较神奇的是，如果加上这段for循坏，能过且0ms，但是如果不加，4ms能过for(int i=0;i<26;i++){if(hash1[i]>0)return false;}return true;} };2.3存在重复元素1
217. 存在重复元素 - 力扣（LeetCode）
哈希表统计数字出现即可。
class Solution { public:bool containsDuplicate(vector<int>& nums) {unordered_map<int,int>hash1;for(auto s:nums){hash1[s]++;if(hash1[s]>=2)return true;}return false;} };2.4存在重复元素2
219. 存在重复元素 II - 力扣（LeetCode）
直接用哈希表判断即可
class Solution { public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,int>hash1;int n=nums.size();for(int i=0;i<n;i++){if(hash1.count(nums[i])){if(i-hash1[nums[i]]<=k)return true;}hash1[nums[i]]=i;}return false;} };2.5字母异位词分组
49. 字母异位词分组 - 力扣（LeetCode）
思路就是利用排序，统计是否是异位词
class Solution { public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>>hash1;for(auto x:strs){auto tmp=x;sort(tmp.begin(),tmp.end());hash1[tmp].push_back(x);}vector<vector<string>>ret(0);for(auto x:hash1){ret.push_back(x.second);}return ret;} };
