15. 3Sum Leetcode Java

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

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Solution:
Two pointers.
Sort the array, and use two pointers left and right to travel across the array and find the right numbers. Clearly if A[left]+A[right]<target, left++ which is the only way to get closer to target. Verse vise. In order to avoid duplicate triplets and save time, each time when we move the pointer, we move it to a new value different with the previous one. 
Time complexity: O(n^2)

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