[Sum] 3Sum

1. Example
s= [-1,0,1,2,-1,-4] and target is 0
A solution set is:
(-1,0,1)
(-1,-1,2)



2. Implementation
Thought1:
Q1: like two Sum
A1: sort the array first
Fix one and the rest use twoSum()
Q1: fix one which one
A1: from the end of the array
Q1: Duplicate solution avoid
A1: same element not being used twice, num[i] in fix one, and the other two in twoSum
Q1: how to combine twoSum and fixed one element to become three sum
A1: list get and add and addAll
FOLLOW UP: solution element in order as original array?

List item = new ArrayList();
 item.add(num[l]);
 item.add(num[r]); 
 // NOTE: no need to check repeated solution since already avoid when iterating res.add(item); // NOTE: more than one solution so iterating l++; r--;
 // avoid Duplicate solution
 while (l < r && num[l] == num[l-1] ) { l++; } 
 while( l< r && num[r] == num[r+1] ) { r--; }

public List> threeSum (int[] num)
{

        List> res = new ArrayList>();


       // valid the input
       if (num == null || num.length <3 data-blogger-escaped--1="" data-blogger-escaped-arrays.sort="" data-blogger-escaped-for="" data-blogger-escaped-i="" data-blogger-escaped-int="" data-blogger-escaped-note:="" data-blogger-escaped-num="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-sort="">1 ; i--)
       {
           // NOTE: avoid repeated solution
           if ( i == num.length || num[i] != num[i+1] )
           {  
             List> curRes = twoSum(num, i-1, 0 - num[i]);
             for (int j = 0 ; j < curRes.size();j++)
             {
                 curRes.get(j).add(num[i]);
             }
             res.addAll(curRes);
           }
       }

       return res;

}


private List> twoSum  (int[] num, int end, int target)
{
        List> res = new ArrayList>();


       //validate the input
       if ( nums == null || nums.length < 2)
       {
            return res;
       }

      
       
       int l =0 ;
       int r = end;
       while (l< r)
       {
             if (  num[l] + num[r] == target )
             {
                   List item = new ArrayList();
                   item.add(num[l]);
                   item.add(num[r]);
                   // NOTE: no need to check repeated solution since already avoid when iterating 
                   res.add(item);
                   // NOTE: more than one solution so iterating
                   l++;
                   r--;

                   // avoid Duplicate solution
                   while (l < r && num[l] == num[l-1] )
                   {
                      l++;
                   }
                   while( l< r && num[r] == num[r+1] )
                   {
                      r--;
                   }

             }
             else if ( num[l] + num[r] > target ) 
             {
                   r--;
             }
             else 
             { 
                   l++
             }

             // NOTE : avoid solution when equal to target

       }
       return res;


}

3. Similar Ones
Combination Sum II
Two Sum
4Sum
3Sum closest