454. 四数相加 II
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> umap; //加的值,以及组合的个数 for(int a : nums1){ for(int b : nums2){ umap[a+b]++; } } 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; } };
心得:这题其实精髓和两数之和很像,将四数转变成两个两数即可。
383. 赎金信
class Solution { public: bool canConstruct(string ransomNote, string magazine) { vector<int> result(26, 0); if(magazine.size() < ransomNote.size()) return false; for(int i = 0; i < magazine.size(); i++) result[magazine[i]-'a']++; for(int j = 0; j < ransomNote.size(); j++){ result[ransomNote[j]-'a']--; if(result[ransomNote[j]-'a'] < 0) return false; } return true; } };
心得:跟四数相加的思路很相似。
15. 三数之和
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[0] > 0) return result; if(i > 0 && nums[i] == nums[i-1]) continue; int start = i+1, end = nums.size()-1; while(start < end){ if(nums[i] + nums[start] + nums[end] < 0) start++; else if(nums[i] + nums[start] + nums[end] > 0) end--; else{ result.push_back(vector<int>{nums[i], nums[start], nums[end]}); while(start < end && nums[end] == nums[end-1]) end--; while(start < end && nums[start] == nums[start+1]) start++; start++; end--; } } } return result; } };
心得:这题要考虑很多种情况。对元素排序后,首先,如果遍历的元素i一开始就大于0,那么立刻结束;接下来针对去重也有很多细节。还是要多想多练。
18. 四数之和
明天再做。
标签:四数,end,nums,int,随想录,454,start,vector,result From: https://www.cnblogs.com/xhhh/p/17189934.html