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.

For example, given array S = [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]]

 

 

tag : two points

 

public class Solution {    public List
     
      
       > fourSum(int[] nums, int target) {        List
       
        
         > result = new ArrayList
         
          
           >(); if(nums == null || nums.length < 4){ return result; } Arrays.sort(nums); for(int i = 0; i < nums.length - 3; i++){ int a = nums[i]; if(i != 0 && nums[i-1] == nums[i]){ continue; } int j; for(j = i + 1; j < nums.length - 2; j ++){ int b = nums[j]; if(j != i + 1 && nums[j-1] == nums[j] ){ continue; } int left = j + 1; int right = nums.length - 1; while(left < right){ int sum = a + b + nums[left] + nums[right]; if(sum == target){ List
           
             list = new ArrayList
            
             (); list.add(a); list.add(b); list.add(nums[left]); list.add(nums[right]); result.add(list); left++; right--; while(left < right && nums[left] == nums[left-1]){ left++; } while(left < right && nums[right+1] == nums[right]){ right--; } }else if(sum < target){ left++; }else{ right--; } } } } return result; }}