[Sum]Two Sum [Facebook]

1. Example
a = [2,7,11,15] , target =9
2+7=9
Return index1 =1, index2 =2;



2. Implementation
Q1: return an index
A1: need to secure original array to find the index
Q1: how many solution set?
A1: Exactly one solution
Thought1: pairs O(n^2)
Thought2: sort O(n log(n))
// NOTE: snippet
if (res[0] == nums[i] || res[1] == nums[i])
{
if (index1 == -1)
{
index1 = i+1;
}
else
{
index2 = i+1;
}
}

// Time:O(n log(n)), Space:O(n) new array
public int[] twoSum (int[] nums, int target)
{
     int[] res = new int[2];
     // valid the input
     if (nums == null || num.length <2)
     {
         return res;
     }
      




     int l = 0;
     int r = nums.length-1;
     while(l < r )
     { 
          if (sorted[l] + sorted[r] == target)
          {
                res[0] = sorted[l]; 
                res[1] = sorted[r];
                break;
          }
          else if ( sorted[l] + sorted[r] > target ) 
          {
                r--;
          }
          else 
          {
                l++;
          }
     }





     int index1 = -1; 
     int index2 = -1;
     for (int i = 0 ; i < nums.length ; i++)
     {
          if (res[0] == nums[i] || res[1] == nums[i])
          {
               if (index1 == -1)
               {
                   index1 = i+1;
               }
               else 
               {
                   index2 = i+1;
               }
          }
     }
     res[0] = index1;
     res[1] = index2;
     return res;

}

3.  Similar Ones
3Sum
4Sum
3Sum closest