电子元器件外贸网站建设,seo网站推广下载,视频网站直播怎么做,网站建设实验的建议和看法代码随想录刷题第六天 | 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和
454.四数相加II
这个题分完组之后和两数其实差不多 得重新复习STL了#xff0c;好多东西全忘了#xff0c;
class Solution {
public:int fourSumCount(vectorint nums1, vect…代码随想录刷题第六天 | 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和
454.四数相加II
这个题分完组之后和两数其实差不多 得重新复习STL了好多东西全忘了
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint,intumap;for(int a:nums1){for(int b:nums2){umap[ab];}}int count 0;for(int c:nums3){for(int d:nums4){if(umap.find(0-(cd))!umap.end()){count count umap[0-(cd)];}}}return count;}
};383. 赎金信
这个题倒是很简单和之前那个题目一样创个数组就行就26个字母
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int nums[27] {0};for(int i 0;i magazine.size();i){nums[magazine[i]-a];}for(int i 0;i ransomNote.size();i){nums[ransomNote[i]-a]--;}for(int i 0;i26;i){if(nums[i] 0)return false;}return true;}
};15 三数之和
重点在于这里返回的是值不需要下标所以用双指针的方法好麻烦的一道题
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorintresult;sort(nums.begin(),nums.end());for(int i 0;inums.size()-2;i){int lefti1;int right nums.size()-1;if(i0nums[i]nums[i-1]){continue;}if(nums[i]0) return result;while(leftright){if(nums[i]nums[left]nums[right] 0){right--;}else if(nums[i]nums[left]nums[right] 0){left;}else{result.push_back(vectorint{nums[i], nums[left], nums[right]});while(leftnums.size()-2nums[left] nums[left1]) left;while(right1nums[right] nums[right-1]) right--;left;right--;}}}return result;}
};18. 四数之和
这里可以有负数所以剪枝操作有问题不能和三数之和一样然后居然还会溢出完全没注意好多细节
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint result;sort(nums.begin(), nums.end());for (int k 0; k nums.size(); k) {if (nums[k] target nums[k] 0) {break; }if (k 0 nums[k] nums[k - 1]) {continue;}for (int i k 1; i nums.size(); i) {if (nums[k] nums[i] target nums[k] nums[i] 0) {break;}if (i k 1 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.size() - 1;while (right left) {if ((long) nums[k] nums[i] nums[left] nums[right] target) {right--;} else if ((long) nums[k] nums[i] nums[left] nums[right] target) {left;} else {result.push_back(vectorint{nums[k], nums[i], nums[left], nums[right]});// 对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;}
};
