题目描述

双指针法

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target){int n=nums.size();vector<vector<int>> res;sort(nums.begin(), nums.end());for(int a=0;a<n;a++){if(nums[a]>target && nums[a]>=0){break;}if(a>=1 && nums[a]==nums[a-1]){continue;}for(int b=a+1;b<n;b++){if(nums[a]+nums[b]>target && nums[a]+nums[b]>=0){break;}if(b>a+1 && nums[b]==nums[b-1]){continue;}int c=b+1, d=n-1;while(c<d){if((long)nums[a]+nums[b]+nums[c]+nums[d]>target){d--;} else if((long)nums[a]+nums[b]+nums[c]+nums[d]<target){c++;} else {res.push_back({nums[a], nums[b], nums[c], nums[d]});while(d>c && nums[d]==nums[d-1]) d--;while(d>c && nums[c]==nums[c+1]) c++;d--;  //找到答案时，双指针同时收缩 c++;}}}}return res;}
};