DAY6 哈希表part02

今日任务

●  454.四数相加II

●  383. 赎金信

●  15. 三数之和

●  18. 四数之和

●  总结

454.四数相加II

题目链接/文章讲解/视频讲解：https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

 1 class Solution {
 2 public:
 3     int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
 4         std:: unordered_map<int,int> map;
 5         for(int a :nums1)
 6             for(int b:nums2)
 7                 map[a+b]++;
 8         
 9         int count=0;
10         for(int c:nums3)
11             for(int d:nums4)
12             {
13                 if(map.find(-c-d)!=map.end()) 
14                     count+=map[-c-d];
15             }
16         return count;
17     }
18 };

383. 赎金信

题目链接/文章讲解：https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

 1 class Solution {
 2 public:
 3     bool canConstruct(string ransomNote, string magazine) {
 4         int len1=ransomNote.size();
 5         int len2=magazine.size();
 6 
 7         int record[26]={0};
 8 
 9         if(len1>len2) return false;
10 
11         for(int i=0;i<len2;i++)
12         {
13             record[magazine[i]-'a']++;
14         }
15         for(int i=0;i<len1;i++)
16         {
17             record[ransomNote[i]-'a']--;
18         }
19         for(int i=0;i<26;i++)
20         if(record[i]<0) return false;
21 
22         return true;
23     }
24 };

15. 三数之和

本题虽然和 两数之和 很像，也能用哈希法，但用哈希法会很麻烦，双指针法才是正解。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

 1 class Solution {
 2 public:
 3     vector<vector<int>> threeSum(vector<int>& nums) {
 4         vector<vector<int>> result;
 5         sort(nums.begin(), nums.end());
 6         // 找出a + b + c = 0
 7         // a = nums[i], b = nums[left], c = nums[right]
 8         for (int i = 0; i < nums.size(); i++) {
 9             // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
10             if (nums[i] > 0) {
11                 return result;
12             }
13             // 错误去重a方法，将会漏掉-1,-1,2 这种情况
14             /*
15             if (nums[i] == nums[i + 1]) {
16                 continue;
17             }
18             */
19             // 正确去重a方法
20             if (i > 0 && nums[i] == nums[i - 1]) {
21                 continue;
22             }
23             int left = i + 1;
24             int right = nums.size() - 1;
25             while (right > left) {
26                 // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
27                 /*
28                 while (right > left && nums[right] == nums[right - 1]) right--;
29                 while (right > left && nums[left] == nums[left + 1]) left++;
30                 */
31                 if (nums[i] + nums[left] + nums[right] > 0) right--;
32                 else if (nums[i] + nums[left] + nums[right] < 0) left++;
33                 else {
34                     result.push_back(vector<int>{nums[i], nums[left], nums[right]});
35                     // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
36                     while (right > left && nums[right] == nums[right - 1]) right--;
37                     while (right > left && nums[left] == nums[left + 1]) left++;
38 
39                     // 找到答案时，双指针同时收缩
40                     right--;
41                     left++;
42                 }
43             }
44 
45         }
46         return result;
47     }
48 };

18. 四数之和

建议： 要比较一下，本题和 454.四数相加II 的区别，为什么 454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。 本题 思路整体和 三数之和一样的，都是双指针，但写的时候 有很多小细节，需要注意，建议先看视频。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html