【力扣hot100】哈希专题

1.两数之和

判断是否有两数和等于target，对于每一个数x判断是否还存在target-x且target-x的下标不是x下标即可。

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n=nums.size();
unordered_map<int,int>mp;
vector<int>ans;
for(int i=0;i<n;i++){
mp[nums[i]]=i;
}
for(int i=0;i<n;i++){
if(mp.count(target–nums[i])&&mp[target–nums[i]]>i){
ans.push_back(i);
ans.push_back(mp[target–nums[i]]);
break;
}
}
return ans;
}
};

49.字母异位词分组

将每一个字符串排序后即可得到键，值是异位词数组。

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>>ans;
unordered_map<string,vector<string>>mp;
for(auto str:strs){
string key=str;
sort(key.begin(),key.end());
mp[key].push_back(str);
}
for(auto i=mp.begin();i!=mp.end();i++){
ans.push_back(i->second);
}
return ans;
}
};

128.最长连续序列

该题题目要求要用O(N)的解法，所以不能直接排序。将数组中的所有数插入哈希集合中，对于集合中每一个数x，判断x-1是否存在，不存在则开始找以x为起点的最长连续序列。

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int>s(nums.begin(),nums.end());
int n=nums.size();
int ans=0;
for(auto i:s){
if(s.contains(i-1)){
continue;
}
int j=i+1;
while(s.contains(j)){
j++;
}
ans=max(ans,j-i);
}
return ans;
}
};