代码随想录算法训练营Day07 | 454.四数相加II、383. 赎金信 、15. 三数之和 、18. 四数之和

---

454.四数相加II

• 题目链接：454. 四数相加 II - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：直接看题解了。

思路与重点

• 首先定义一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
• 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
• 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
• 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
• 最后返回统计值 count 就可以了

class Solution {
public:int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中for (int a : A) {for (int b : B) {umap[a + b]++;}}int count = 0; // 统计a+b+c+d = 0 出现的次数// 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。for (int c : C) {for (int d : D) {if (umap.find(0 - (c + d)) != umap.end()) {count += umap[0 - (c + d)];}}}return count;}
};

383. 赎金信

• 题目链接：383. 赎金信 - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：一遍AC。

思路与重点

• 用一个长度为26的数组来记录magazine里字母出现的次数。

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int magazineMap[26] = {0};for(char ch : magazine){magazineMap[ch - 'a']++;}for(char ch : ransomNote){magazineMap[ch - 'a']--;if(magazineMap[ch - 'a'] < 0) return false;}return true;}
};

15. 三数之和

• 题目链接：15. 三数之和 - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：直接看题解了。

思路与重点

• 这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。这道题目使用双指针法要比哈希法高效一些。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;sort(nums.begin(), nums.end());for(int i = 0; i < nums.size() - 2; i++){if(i > 0 && nums[i] == nums[i-1]) continue;int j = i + 1;int k = nums.size() - 1;while(j < k){if(nums[i] + nums[j] + nums[k] == 0){ans.push_back({nums[i], nums[j], nums[k]});while(j < k && nums[j] == nums[j+1]) j++;while(j < k && nums[k] == nums[k-1]) k--;j++;k--;}else if(nums[i] + nums[j] + nums[k] > 0) k--;else j++;}}return ans;}
};

18. 四数之和

• 题目链接：18. 四数之和 - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：调试几次后AC。

思路与重点

• 本题和15. 三数之和解法类似，采用双指针将原本暴力O(n^{4)的解法，降为O(n}3)的解法。
• 尤其需要注意题目中数字的范围为-10⁹ <= nums[i] <= 10⁹ ，而int的范围是-2×10⁹ 到2×10⁹ ，所以int的四数相加会造成溢出，需要转换为long类型。
• nums.size()返回的数字类型是unsigned int，所以nums.size() - 3会造成负溢出，此时数值不正确导致循环不正确。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ans;sort(nums.begin(), nums.end());for(int a = 0; a < (int)nums.size() - 3; a++){if(a > 0 && nums[a] == nums[a-1]) continue;for(int b = a + 1; b < nums.size()- 2; b++){if(b > a + 1 && nums[b] == nums[b-1]) continue;int c = b + 1;int d = nums.size() - 1;while(c < d){if((long)nums[a] + nums[b] + nums[c] + nums[d] == target){ans.push_back({nums[a], nums[b], nums[c], nums[d]});while(c < d && nums[c] == nums[c+1]) c++;while(c < d && nums[d] == nums[d-1]) d--;c++;d--;}else if((long)nums[a] + nums[b] + nums[c] + nums[d] > target) d--;else c++;}}}return ans;}
};