Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
1 class Solution { 2 public: 3 vector<vector<int>> fourSum(vector<int>& a, int target) { 4 vector<vector<int>> res; 5 const int n = a.size(); 6 if (n < 4) return res; 7 std::sort(a.begin(),a.end()); 8 for (int i = 0; i < n-3; ++i) { 9 if(i!=0 && a[i]==a[i-1]) {continue;} //去重 10 for (int j = i+1; j < n-2; ++j) { 11 if(j!=i+1 && a[j]==a[j-1]){continue;} //去重 12 int low = j+1; 13 int high = n-1; 14 while (low < high) { 15 int sum = a[i]+a[j]+a[low]+a[high]; 16 if (sum > target) { 17 high--; 18 } else if (sum < target) { 19 low++; 20 } else { 21 vector<int> tep = {a[i],a[j],a[low],a[high]}; 22 res.emplace_back(tep); 23 while(low <high && a[low]==a[low+1]) {low++;}//去重 24 while(low <high && a[high]==a[high-1]) {high--;}//去重 25 low++; 26 high--; 27 } 28 } 29 30 } 31 } 32 return res; 33 } 34 };
1 class Solution { 2 public List<List<Integer>> fourSum(int[] nums, int target) { 3 List<List<Integer>> res = new LinkedList<>(); 4 if (nums.length<4) return res; 5 Arrays.sort(nums); 6 for(int i=0;i<nums.length-3;i++){ 7 if(i>0&&nums[i]==nums[i-1]) continue; 8 for(int j=i+1;j<nums.length-2;j++){ 9 if(j>i+1&&nums[j]==nums[j-1]) continue; 10 11 int lo = j+1,hi = nums.length-1; 12 while(lo<hi){ 13 int sum = nums[i]+nums[j]+nums[lo]+nums[hi]; 14 if(sum==target){ 15 res.add(Arrays.asList(nums[i],nums[j],nums[lo],nums[hi])); 16 17 //答案去重 18 while(lo<hi&&nums[lo]==nums[lo+1]) lo++; 19 while(lo<hi&&nums[hi]==nums[hi-1]) hi--; 20 21 lo++; 22 hi--; 23 } 24 25 else if(sum<target) lo++; 26 else hi--; 27 } 28 29 } 30 } 31 return res; 32 } 33 }