Leetcode|454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18. 四数之和

15.三数之和

哈希解法：

用俩个for循环求出，所需的a和b，再用哈希表，判断剩余的那个c是否在数组

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());// 找出a + b + c = 0// a = nums[i], b = nums[j], c = -(a + b)for (int i = 0; i < nums.size(); i++) {// 排序之后如果第一个元素已经大于零，那么不可能凑成三元组if (nums[i] > 0) {break;}if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重continue;}unordered_set<int> set;for (int j = i + 1; j < nums.size(); j++) {if (j > i + 2&& nums[j] == nums[j-1]&& nums[j-1] == nums[j-2]) { // 三元组元素b去重continue;}int c = 0 - (nums[i] + nums[j]);if (set.find(c) != set.end()) {result.push_back({nums[i], nums[j], c});set.erase(c);// 三元组元素c去重} else {set.insert(nums[j]);}}}return result;}
};

双指针解法：

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();i++){if(nums[i] > 0){return result;}//i元素的去重if(i > 0&& nums[i] == nums[i-1]){continue;}int left = i + 1;int right = nums.size() - 1;//left 和 right元素的去重,相同就停止，因为要求的是三个元素，而非俩个元素while(right > left){if(nums[i] + nums[left] + nums[right] >0){right--;}else if(nums[i] + nums[left] + nums[right] < 0){left++;}else{result.push_back(vector<int>{nums[i],nums[left],nums[right]});//去重逻辑应该放在找到一个三元组之后//防止漏掉{0,0,0}这个三元组while(right>left&&nums[right] == nums[right-1]) right--;while(right>left&&nums[left] == nums[left+1]) left++;left++;right--;}}}return result;}
};

454.四数相加

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map <int,int> umap; //key为a和b的值，value为a和b的值出现的次数//记录，a和b and a和b出现的次数for(int a: nums1){for(int b: nums2){umap[a+b]++;//俩数的和and次数}}int count = 0;for(int c:nums3){for(int d:nums4){if(umap.find(0 - (c+d))!=umap.end()){count += umap[0-(c+d)];}}}return count;}
};

18.四数之和

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;sort(nums.begin(),nums.end());for(int k = 0;k < nums.size();k++){//剪枝 if(nums[k] > target) return result;这错误的，target不为0// 去重if(k > 0 && nums[k] == nums[k-1]){continue;}for(int i = k + 1;i < nums.size();i++){//去重if(i > k + 1 && nums[i] == nums[i-1]){continue;}int left = i + 1;int right = nums.size() - 1;while(right > left){if(nums[k] + nums[i] > target - nums[left] - nums[right]){right--;}else if(nums[k] + nums[i] < target - nums[left] - nums[right]){left++;}else{result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});while(right>left&&nums[right] == nums[right-1]) right--;while(right>left&&nums[left] == nums[left+1]) left++;right--;left++;}}}}return result;}
};

383,赎金,此题与求解异位字母是同种思路

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int record[26] = {0};if(ransomNote.size() > magazine.size()) return false;for(int i = 0;i < magazine.length();i++){record[magazine[i] - 'a']++;   //统计个数，映射求结果}for(int j = 0;j<ransomNote.length();j++){record[ransomNote[j] - 'a']--;}for(int i = 0;i < 26; i++){if(record[i] < 0){return false;}}return true;}
};