飞舞大学生成为算法糕手Day 7 | 四数相加Ⅱ、赎金信、三数之和、四数之和

四数相加Ⅱ

[https://programmercarl.com/0454.四数相加II.html#思路]

思路

使用unordered_map，因为需要记录出现的次数。然后两两一组寻找符合要求的匹配，重点是掌握unordered_map的用法

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> map;for(int &i : nums1){for(int &j : nums2){map[i + j]++;}} int count = 0;for(int &i : nums3){for(int &j : nums4){if(map.find(-i - j) != map.end()){count += map[-i - j];}}}return count;}
};

总结

• 初始化：unordered_map<int,int> a;
• 访问：a[i]
• 查找：类似于unordered_set

---

赎金信

[https://programmercarl.com/0383.赎金信.html#思路]

---

解法

依旧是使用unordered_map，比较常规，和前面的字母异位词差不多。

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {unordered_map<char,int> usable;for(char &p : magazine){usable[p]++;}for(char &p : ransomNote){usable[p]--;if(usable[p] < 0) return false;}return true;}
};

---

三数之和

[https://programmercarl.com/0015.三数之和.html#思路]

---

解法

本题使用双指针解决（三指针），因为要去重，所以不方便使用哈希表。
先对数组进行排序，然后用一个i遍历数组，初始为i = 0，如果nums[i]在排序后大于0，则直接break。然后设置left = i + 1，right = nums.size() - 1，当三个数加起来大于0时right--；小于0时left++；等于0时将三个数放入结果数组
关于去重：

• i的去重。当nums[i] == nums[i - 1]时continue，因为如果是i == i + 1时continue，语义是结果组中不能出现相同元素，像（-1，-1，2）就漏掉了。所以应该是i == i - 1，这样才能跳过已经使用了的元素。
• left、right的去重。这里不用和上一个比，和下一个比就可以。因为在比较前已经将结果加进结果数组了，之后的比较都是在已经存好结果的条件下比，直接看下一个和已经存进去的一不一样就可以了。

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

总结

right和left的去重要放在else里，不能提前拿出来。

---

四数之和

[https://programmercarl.com/0018.四数之和.html#思路]

---

解法

对j的去重，要放在后面，和left、right的去重逻辑类似，不可以采用和i一样的，因为当nums[i] == nums[j - 1]的时候会直接跳过

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;sort(nums.begin(),nums.end());if(nums.size() < 4) return result;for(int i = 0;i < nums.size() - 3;i++){for(int j = i + 1;j < nums.size() - 2;j++){if(nums[i] > target && nums[i] > 0) break;if(i > 0 && nums[i] == nums[i - 1]) continue;int left = j + 1;int right = nums.size() - 1;while(left < right){if((long)nums[i] + nums[j] + nums[left] + nums[right] < target) left++;else if((long)nums[i] + nums[j] + nums[left] + nums[right] > target) right--;else{result.push_back({nums[i],nums[j],nums[left],nums[right]});while(left < right && nums[left] == nums[left + 1]) left ++;while(left < right && nums[right] == nums[right - 1]) right--;while(j < nums.size() - 2 && nums[j] == nums[j + 1]) j++;right--;left++;}}}}return result;}
};