18. 4Sum Leetcode Java

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, a ≤ b ≤ c ≤ d)
• 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)

Solution:
Two pointer:
Very similar to 3Sum, just add another pointer to track the 4th number.
Time complexity: O(n^3)

  public List<List<Integer>> fourSum(int[] num, int target) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    if(num==null || num.length<4) return res;  
    Arrays.sort(num);  
    for(int i=0;i<num.length-3;i++){  
      for(int j=i+1;j<num.length-2;j++){  
        int l=j+1;  
        int r=num.length-1;  
        while(l<r){  
          if(num[i]+num[j]+num[l]+num[r]==target){  
            List<Integer> temp=new ArrayList<Integer>();  
            temp.add(num[i]);  
            temp.add(num[j]);  
            temp.add(num[l]);  
            temp.add(num[r]);  
            res.add(temp);  
            while(l+1<r && num[l+1]==num[l]) l++;  
            l++;  
            while(l<r-1 && num[r-1]==num[r]) r--;  
            r--;  
          }  
          else if(num[i]+num[j]+num[l]+num[r]<target) l++;  
          else r--;  
        }  
        while(j+1<num.length-2 && num[j+1]==num[j]) j++;  
      }  
      while(i+1<num.length-3 && num[i+1]==num[i]) i++;  
    }  
    return res;  
   }