熟悉hash映射,用key判断是否对象存在或者存在个数,在其他问题种常用来记录key(键值)是否存在(或者存在个数),用来if判断。
1. 两数之和 - 力扣(LeetCode)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
unordered_map<int,int> hash;
for(int i=0;i<nums.size();i++){
int target_i=target-nums[i];
if(hash.count(target_i)){
ret.push_back(i);
ret.push_back(hash[target_i]);
}
hash.insert({nums[i],i});
}
return ret;
}
};
面试题 01.02. 判定是否互为字符重排 - 力扣(LeetCode)
class Solution {
public:
bool CheckPermutation(string s1, string s2) {//类似异或词比较,但是之前的滑动数组需要从数组中找一个元素,利用有效字符的个数。
if(s1.size()!=s2.size())
return false;
int hash[26]={0};
for(char &val:s1){
hash[val-'a']++;
}
for(char &val:s2){
if(--hash[val-'a']<0){
return false;
}
}
return true;
}
};
217. 存在重复元素 - 力扣(LeetCode)
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> hash;
for(int &val:nums){
if(++hash[val]>1) return true;
}
return false;
}
};
219. 存在重复元素 II - 力扣(LeetCode)
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;
}
};
. - 力扣(LeetCode)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ret;
unordered_map<string,vector<string>> hash;//***1***是unoedered——map非vector
//关键异或词的特点,排序后单词相同,将tmp排序后,依据tmp的映射关系得到原string存入数组
for(string& str1:strs){
string tmp=str1;
sort(tmp.begin(),tmp.end());
hash[tmp].push_back(str1);
}
for(auto& [a,b]:hash){
ret.push_back(b);
}
return ret;
}
};