#### LeetCode #18 – 4Sum [双指针]

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, abcd)
• The solution set must not contain duplicate quadruplets.

class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
if(nums.size() < 4) return res;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size()-3; ++i) {
if(i && nums[i]==nums[i-1]) continue;
for(int j = i + 1; j < nums.size()-2; ++j) {
if(j != i+1 && nums[j]==nums[j-1]) continue;
int sum = target - (nums[i]+nums[j]);
int l = j + 1, r = nums.size()-1;
while (l < r) {
if(l != j+1 && nums[l]==nums[l-1]) ++l;
else if(r != nums.size()-1 && nums[r]==nums[r+1]) --r;
else if(nums[l] + nums[r] < sum) ++l;
else if(nums[l] + nums[r] > sum) --r;
else {
vector<int> t = {nums[i], nums[j], nums[l], nums[r]};
res.push_back(t);
++l, --r;
}
}
}
}
return res;
}
};