【LC刷题】DAY04：454 383 15 18
文章目录
- 【LC刷题】DAY04：454 383 15 18
- 454. 四数相加 II [link](https://leetcode.cn/problems/4sum-ii/description/)
- 383. 赎金信 [link](https://leetcode.cn/problems/ransom-note/description/)
- 15. 三数之和 [link](https://leetcode.cn/problems/3sum/description/)
- 18. 四数之和 [link](https://leetcode.cn/problems/4sum/description/)
454. 四数相加 II link
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> countAB;for(int u : nums1){for(int v : nums2){++countAB[u + v];}}int ans = 0;for(int u : nums3){for(int v : nums4){if(countAB.count(-u-v)){ans += countAB[-u-v];}}}return ans;}
};
383. 赎金信 link
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if(ransomNote.size() > magazine.size()){return false;}unordered_map<char, int> s_map;for(char s : magazine){s_map[s] ++;}for(char s : ransomNote){if(s_map.find(s) == s_map.end() || --s_map[s] < 0){return false;}}return true;}
};
15. 三数之和 link
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());vector<vector<int>> ans;// 枚举 afor (int first = 0; first < n; ++first) {// 需要和上一次枚举的数不相同if (first > 0 && nums[first] == nums[first - 1]) {continue;}// c 对应的指针初始指向数组的最右端int third = n - 1;int target = -nums[first];// 枚举 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚举的数不相同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 需要保证 b 的指针在 c 的指针的左侧while (second < third && nums[second] + nums[third] > target) {--third;}// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if (second == third) {break;}if (nums[second] + nums[third] == target) {ans.push_back({nums[first], nums[second], nums[third]});}}}return ans;}
};
18. 四数之和 link
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> quadruplets;if (nums.size() < 4) {return quadruplets;}sort(nums.begin(), nums.end());int length = nums.size();for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
};
