4.4刷题记录（哈希表）

1.242. 有效的字母异位词 - 力扣（LeetCode）

class Solution {
public:bool isAnagram(string s, string t) {unordered_map<char,int>cnt_s,cnt_t;for(int i=0;i<s.size();i++){cnt_s[s[i]]++;}for(int i=0;i<t.size();i++){cnt_t[t[i]]++;}if(cnt_s==cnt_t){return true;}return false;}
};

其中unorder_map判断是否相等的逻辑通过以下来实现

for (const auto& pair : map1) {// 在第二个 unordered_map 中查找当前键auto it = map2.find(pair.first);// 如果找不到键，或者键对应的值不相等，返回 falseif (it == map2.end() || it->second != pair.second) {return false;}}

2.383. 赎金信 - 力扣（LeetCode）

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {unordered_map<char,int>cnt_r,cnt_m;for(int i=0;i<ransomNote.size();i++){cnt_r[ransomNote[i]]++;}for(int i=0;i<magazine.size();i++){cnt_m[magazine[i]]++;}for(const auto& item1 : cnt_r){auto item2=cnt_m.find(item1.first);if(item2==cnt_m.end()||item1.second>item2->second){return false;}}return true;}
};

注意比较大小的时候find查找的是first的值，判断second是否相等的时候一个是.一个是箭头

3.349. 两个数组的交集 - 力扣（LeetCode）

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int>answer;unordered_map<int,int>cnt1,cnt2;for(int i=0;i<nums1.size();i++){cnt1[nums1[i]]++;}for(int i=0;i<nums2.size();i++){cnt2[nums2[i]]++;}for(const auto& item1 : cnt1){auto item2=cnt2.find(item1.first);if(item2!=cnt2.end()){answer.push_back(item2->first);}}return answer;}
};

4.49. 字母异位词分组 - 力扣（LeetCode）

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {//首先进行排序unordered_map<string,vector<string>>cnt;for(string str:strs){string key=str;sort(key.begin(),key.end());cnt[key].push_back(str);}vector<vector<string>>ans;for(const auto& item :cnt){ans.push_back(item.second);}return ans;}
};

先排序然后将排序过后的放在一个vector，简单高效，值得学习

5.438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

class Solution {
public:vector<int> findAnagrams(string s, string p) {unordered_map<char,int>cnts,cntp;vector<int>ans;if(s.size()<p.size()){return ans;}for(int i=0;i<p.size();i++){cntp[p[i]]++;cnts[s[i]]++;}if(cntp==cnts){ans.push_back(0);}for(int i=p.size();i<s.size();i++){//现在删除左面的元素if(--cnts[s[i-p.size()]]==0){cnts.erase(s[i-p.size()]);}//增加右边的元素cnts[s[i]]++;if(cntp==cnts){ans.push_back(i-p.size()+1);}}return ans;}
};

6.350. 两个数组的交集 II - 力扣（LeetCode）

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int>cnt1,cnt2;vector<int>answer;for(int i=0;i<nums1.size();i++){cnt1[nums1[i]]++;}for(int i=0;i<nums2.size();i++){cnt2[nums2[i]]++;}for(const auto& item1:cnt1){auto item2=cnt2.find(item1.first);if(item2==cnt2.end()){continue;}else{for(int i=0;i<min(item1.second,item2->second);i++){answer.push_back(item1.first);}}}return answer;}
};

7.202. 快乐数 - 力扣（LeetCode）

第一种方法比较巧妙（借助快慢指针），第二种比较普遍（利用hash_set）。

class Solution {
public:int sumsqure(int n){int sum=0;while(n!=0){int a=n%10;sum+=a*a;n=n/10;}return sum;} bool isHappy(int n) {int fast=n,slow=n;do{fast=sumsqure(fast);fast=sumsqure(fast);slow=sumsqure(slow);}while(fast!=slow);return fast==1;}
};

class Solution {
public:// 取数值各个位上的单数之和int getSum(int n) {int sum = 0;while (n) {sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {unordered_set<int> set;while(1) {int sum = getSum(n);if (sum == 1) {return true;}// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return falseif (set.find(sum) != set.end()) {return false;} else {set.insert(sum);}n = sum;}}
};

8.1. 两数之和 - 力扣（LeetCode）

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int>ans;unordered_map<int,int>cnt;for(int i=0;i<nums.size();i++){auto item = cnt.find(target-nums[i]);if(item!=cnt.end()){ans.push_back(i);ans.push_back(item->second);break;}cnt.insert(pair<int,int>(nums[i],i));}return ans;}
};

9.454. 四数相加 II - 力扣（LeetCode）

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int>sum1,sum2;//1.首先存储nums1,nums2for(int i=0;i<nums1.size();i++){for(int j=0;j<nums2.size();j++){sum1[nums1[i]+nums2[j]]++;}}//2.进行求和int count=0;for(int i=0;i<nums3.size();i++){for(int j=0;j<nums4.size();j++){auto item=sum1.find(0-nums3[i]-nums4[j]);if(item!=sum1.end()){count+=item->second;}}}//3.输出return count;}
};

10.15. 三数之和 - 力扣（LeetCode）

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {unordered_map<int, int> count; // 统计每个数字的出现次数set<vector<int>> ans_set; // 用于去重vector<vector<int>> ans; // 最终结果// 统计每个数字的出现次数for (int num : nums) {count[num]++;}// 遍历所有可能的两个数字组合for (const auto& [a, count_a] : count) {for (const auto& [b, count_b] : count) {int c = -(a + b); // 第三个数字// 检查第三个数字是否存在if (count.find(c) != count.end()) {// 创建一个临时三元组vector<int> triplet = {a, b, c};sort(triplet.begin(), triplet.end()); // 排序以便去重// 检查是否满足条件if (a == b && b == c) { // a == b == cif (count[a] >= 3) {ans_set.insert(triplet);}} else if (a == b) { // a == b != cif (count[a] >= 2 && count[c] >= 1) {ans_set.insert(triplet);}} else if (b == c) { // a != b == cif (count[b] >= 2 && count[a] >= 1) {ans_set.insert(triplet);}} else if (a == c) { // b != a == cif (count[a] >= 2 && count[c] >= 1) {ans_set.insert(triplet);}} else { // a != b != cif (count[a] >= 1 && count[b] >= 1 && count[c] >= 1) {ans_set.insert(triplet);}}}}}// 将结果从集合转换为向量for (const auto& vec : ans_set) {ans.push_back(vec);}return ans;}
};

另一种方法：双指针法（此代码及其考虑去重问题，而且运用到了双指针。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//1.使用双指针法sort(nums.begin(),nums.end());vector<vector<int>>answer;for(int i=0;i<nums.size();i++){if(nums[i]>0){return answer;}//首先对nums[i]去重if(i>0&&nums[i-1]==nums[i]){continue;}int left=i+1,right=nums.size()-1;while(left<right){if(nums[i]+nums[left]+nums[right]==0){answer.push_back({nums[i],nums[left],nums[right]});//接下来对left和right进行去重while(left<right　&&　nums[left]==nums[left+1]){left++;}while(right>left && nums[right]==nums[right-1]){right--;}left++;right--;}else if(nums[i]+nums[left]+nums[right]>0){right--;}else{left++;}}}return answer;}
};

11.18. 四数之和 - 力扣（LeetCode）​​​​​​

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> ans;for (int i = 0; i < nums.size(); i++) {if(nums[i]>target&&nums[i]>=0){break;}if(i>0&& nums[i]==nums[i-1]){continue;}for (int j = i + 1; j < nums.size(); j++) {if(nums[i]+nums[j]>target&&(nums[i]+nums[j])>=0){break;}if (j>i+1 && nums[j] == nums[j - 1]) {continue;}int left = j + 1, right = nums.size() - 1;while (left < right) {if ((long)nums[i] + nums[j] + nums[left] + nums[right] == target) {ans.push_back({nums[i], nums[j],nums[left], nums[right]});// 接下来对left和right进行去重while (left < right && nums[left] == nums[left + 1]) {left++;}while (right > left && nums[right] == nums[right - 1]) {right--;}left++;right--;} else if ((long)nums[i]+nums[j] + nums[left] + nums[right] > target) {right--;} else {left++;}}}}return ans;}
};