本文主要是介绍代码随想录训练营第六天 454四数相加II 383赎金信 15三数之和 18四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第一题：
原题链接：454. 四数相加 II - 力扣（LeetCode）
思路：
将四个数组分成两两 两个组合，先对前面两个数组进行操作
定义unordered_map<int, int> map,将第一个和第二个数组中的元素相加并填入map中，记录相加之后元素的值对应出现的个数。
然后再对第三和第四个数组进行操作
定义一个值target为第三和第四数组中元素相加后取反，在map中查找该元素是否存在，若存在结果+=map[target]。因为存在证明在第一个和第二个数组中存在对应元素出现的个数。
代码如下：
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> map;for(auto a : nums1){for(auto b : nums2){map[a + b] += 1;}}int res = 0;for(auto c : nums3){for(auto d : nums4){int target = -(c + d);if(map.find(target) != map.end()){res += map[target];}}}return res;}
};第二题：
原题链接：383. 赎金信 - 力扣（LeetCode）
思路：
定义unordered_map<char, int> map，遍历第一个字符串，记录每个字符出现的次数，
遍历第二个字符串，当出现和map中存在的字符，记录的次数减一，
最后遍历整个map，观察每个pair中的第二值是否>0，是则说明无法构成，返回false，反之为true；
代码如下：
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {unordered_map<char, int> map;for(int i = 0; i < ransomNote.size(); i++){map[ransomNote[i]] += 1;}for(int i = 0; i < magazine.size(); i++){if(map.find(magazine[i]) != map.end()){map[magazine[i]] -= 1;}}for(auto x : map){if(x.second > 0){return false;}}return true;}
};第三题：
原题链接：15. 三数之和 - 力扣（LeetCode）
思路：
此题用双指针更好做一些。
首先对数组进行排序，这点很关键，可以剪枝。应为题目要求不能包含重复的三元组，因此不能出现重复的元素。当我们排完序之后，想同的元素就紧挨在一起便于我们操作
遍历整个数组，然后定义两根指针分别指向当前遍历的位置加一和数组末尾的位置。先判断我们当前遍历的位置的值是否大于0，如果大于0直接返回res，因为排过序后当前值大于0后面的值也大于0。剪枝操作：当前元素和前一个元素的值相同，可以直接跳过。
接在在right > left的循环里判断三数之和是否大于0，大于0right--，如果小于0left++，如果等于0，将这三个值插入res中，然后判断left的值和left+1的值是否相同，相同也要跳过。right同理。
最后返回res。
代码如下：
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(), nums.end());for(int i = 0; i < nums.size(); i++){if(nums[i] > 0) return res;if(i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, 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{res.push_back({nums[i], nums[left], nums[right]});while(right > left && nums[right - 1] == nums[right]) right--;while(right > left && nums[left + 1] == nums[left]) left++;left++;right--;}}}return res;}
};第四题
原题链接：18. 四数之和 - 力扣（LeetCode）
思路：
和上一题相似，就是在套一层循环.
代码如下：
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;sort(nums.begin(), nums.end());for(int k = 0; k < nums.size(); k++){if(nums[k] > target && nums[k] >= 0) return res;if(k > 0 && nums[k] == nums[k - 1]) continue;for(int i = k + 1; i < nums.size(); i++){if(nums[i] + nums[k]> target && nums[k] >= 0){return res;}if(i > k + 1 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = nums.size() - 1;while(right > left){if((long)nums[i] + nums[k] + nums[left] + nums[right] < target){left++;}else if((long)nums[i] + nums[k] + nums[left] + nums[right] > target){right--;}else{res.push_back({nums[i], nums[k], nums[left], nums[right]});while(right > left && nums[right - 1] == nums[right]) right--;while(right > left && nums[left + 1] == nums[left]) left++;right--;left++;}}}}return res;}
};这篇关于代码随想录训练营第六天 454四数相加II 383赎金信 15三数之和 18四数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
