四数之和 https://leetcode-cn.com/problems/4sum/ 四指针问题我是跟着一个题解学到的。然后呢,发现了如下问题。 当我如下代码的时候是通过的:
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target){ vector<vector<int>> res; sort(nums.begin(),nums.end()); int N=nums.size(); if(N<4) return res; int a,b,c,d; for(a=0;a<=N-4;a++){ while(a>0&&nums[a-1]==nums[a]) a++; for(b=a+1;b<=N-3;b++){ while(b>a+1&&nums[b-1]==nums[b]) b++; if(b>a+1&&nums[b]==nums[b-1])continue; c=b+1; d=N-1; while(c<d){ //开始比较数值 if(nums[a]+nums[b]+nums[c]+nums[d]<target) c++; else if(nums[a]+nums[b]+nums[c]+nums[d]>target) d--; else{ res.push_back({nums[a],nums[b],nums[c],nums[d]}); while(c<d&&nums[c+1]==nums[c]) c++; while(c<d&&nums[d]==nums[d-1]) d--; c++; d--;//改变 } } } } return res; } };然而我却一开始却一直错在一个简单的样例上,并且最奇怪的是输出了一个和不为target的答案。 如下:
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target){ vector<vector<int>> res; sort(nums.begin(),nums.end()); int N=nums.size(); if(N<4) return res; int a,b,c,d; for(a=0;a<=N-4;a++){ while(a>0&&nums[a-1]==nums[a]) a++; for(b=a+1;b<=N-3;b++){ while(b>a+1&&nums[b-1]==nums[b]) b++; if(b>a+1&&nums[b]==nums[b-1])continue; c=b+1; d=N-1; while(c<d){ //开始比较数值 if(nums[a]+nums[b]+nums[c]+nums[d]<target) c++; /*else*/ if(nums[a]+nums[b]+nums[c]+nums[d]>target) d--; else{ res.push_back({nums[a],nums[b],nums[c],nums[d]}); while(c<d&&nums[c+1]==nums[c]) c++; while(c<d&&nums[d]==nums[d-1]) d--; c++; d--;//改变 } } } } return res; } };不错,将那个else去掉之后就出现了这样的结果。然后不想多写了,因为我要去上思修课了。
