哈希表的介绍和使用
今天，我们来介绍的是哈希表，哈希表主要用于对数据的出现次数统计，查重。利用的容器主要有vector、map/set、ordered_map/ordered_set等。
下面我们来看几道例题：
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};
}
};
2.
class Solution {
public:
bool CheckPermutation(string s1, string s2) {
int n=s1.size(),m=s2.size();
if(n!=m) return false;
int hash[26]={0};
for(int i=0;i<n;i++){
hash[s1[i]-'a']++;
}
for(int i=0;i<n;i++){
hash[s2[i]-'a']--;
if(hash[s2[i]-'a']<0) return false;
}
return true;
}
};
3.
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
};
4.
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])){
if(i-hash[nums[i]]<=k) return true;
}
hash[nums[i]]=i;
}
return false;
}
};
5.
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> hash;
for(auto& e : strs){
string ret=e;
sort(ret.begin(),ret.end());
hash[ret].push_back(e);
}
vector<vector<string>> a;
for(auto& [x,y] : hash){
a.push_back(y);
}
return a;
}
};
全部结束了，期待下次交流！！！
