双指针用起来！
双指针的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
if(nums.size()<3)
return ans;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-2;++i)
{
if(nums[i]>0)
return ans;
if(i>0&&nums[i]==nums[i-1])
continue;
int l=i+1;
int r=nums.size()-1;
while(l<r)
{
if(nums[i]+nums[l]+nums[r]==0)
{
ans.push_back({nums[i],nums[l],nums[r]});
while(l<r&&nums[l+1]==nums[l])
++l;
while(l<r&&nums[r-1]==nums[r])
--r;
++l;
--r;
}
else if(nums[i]+nums[l]+nums[r]<0)
++l;
else
--r;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
if(nums.size()<4)
return ans;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-3;++i)
{
if(target<=0&&nums[i]>0)
break;
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target)
break;
if(i>0&&nums[i]==nums[i-1])
continue;
int newtarget=target-nums[i];
for(int j=i+1;j<nums.size()-2;++j)
{
if(j>i+1&&nums[j]==nums[j-1])
continue;
int l=j+1;
int r=nums.size()-1;
while(l<r)
{
if(nums[j]+nums[l]+nums[r]==newtarget)
{
ans.push_back({nums[i],nums[j],nums[l],nums[r]});
while(l<r&&nums[l+1]==nums[l])
++l;
while(l<r&&nums[r-1]==nums[r])
--r;
++l;
--r;
}
else if(nums[j]+nums[l]+nums[r]<newtarget)
++l;
else
--r;
}
}
}
return ans;
}
};
|
这两道题都是求几数之和，按这两个套路可以无限套娃做循环得出大于4个数求和的结果，不过相应地要消耗的时间会成倍增加。
这题求的结果是最接近target的三数之和，因此ans初值可以为该数组的前三个数，接下来的套路和三数之和差不多，排序+双指针，先判断sum==target,成功直接跳出，否则做绝对值大小的判断，小于则刷新ans值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int ans=nums[0]+nums[1]+nums[2];
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();++i)
{
int l=i+1;
int r=nums.size()-1;
while(l<r)
{
int sum=nums[i]+nums[l]+nums[r];
if(target==sum)
return sum;
if(abs(target-sum)<abs(target-ans))
ans=sum;
else if(nums[i]+nums[l]+nums[r]<target)
++l;
else
--r;
}
}
return ans;
}
};
|