Leetcode 18. 4Sum

18. 4Sum

Total Accepted: 80288
Total Submissions: 328279
Difficulty: Medium

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: The solution set must not contain duplicate quadruplets.

思路：基本思想和Leetcode 16. 3Sum Closest类似，只是数的个数变为4。

代码：

 1 class Solution {
 2 public:
 3     vector<vector<int> > fourSum(vector<int>& nums, int target) {
 4         vector<vector<int> > res;
 5         int n=nums.size();
 6         if(n<4) return res;
 7         sort(nums.begin(),nums.end());
 8         int i,j,k,l,ans;
 9         for(i=0;i<n-3;i++){
10             if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
11             if(nums[i]+nums[n-1]+nums[n-2]+nums[n-3]<target) continue;
12             while(i>0&&nums[i]==nums[i-1]) i++;
13             for(j=i+1;j<n-2;j++){
14                 if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
15                 if(nums[i]+nums[n-1]+nums[n-2]+nums[j]<target) continue;
16                 while(j>i+1&&nums[j]==nums[j-1]) j++;
17                 k=j+1;
18                 l=n-1;
19                 while(k<l){
20                     ans=nums[i]+nums[j]+nums[k]+nums[l];
21                     if(target==ans){
22                         res.push_back({nums[i],nums[j],nums[k],nums[l]});
23                         while(k<l&&nums[k]==nums[k+1]) k++;
24                         while(k<l&&nums[l]==nums[l-1]) l--;
25                     }
26                     if(ans>=target) l--;
27                     if(ans<=target) k++;
28                 }
29             }
30         }
31         return res;
32     }
33 };