3Sum

5/22/2018 update
这次把在外层循环的去重搞忘了。但是自己想到了如何在内层循环去重的l < r这个控制条件。
-------------------------------------------------------------------------------------------------------------------


2/20/2018 update
幸亏做了第二遍，彻底地把这道题搞懂了。之前的总结还算到位。说一下去除内层循环重复。当找到答案的时候才去重复，没有找到答案重复会自然跳过。比如数组 1,1,3,4,5,5，如果找target 7, 那么l会一直增大知道3，r会一直减小直到5。调整l, r位置应该在去除重复之后，去寻找额外的解。

Solution:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            // remove duplicate
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];
            while (l < r) {
                if (nums[l] + nums[r] == sum) {
                    res.add(Arrays.asList(nums[l], nums[r], nums[i]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                } else if (nums[l] + nums[r] < sum) {
                    l++;
                } else {
                    r--;
                }
            }
        }

        return res;
    }
}

------------------------------------------------------------------------------------------------------

思路：
把a+b+c=0转换成a+b=-c，就变成了 2 sum问题。这道题的难点是去重复。
1.每一次找3 sum，是从当前数的右边找，不然会重复。left = i+1, right = nums.length - 1.
2.在外层循环也需要去重复。
3. 内层循环去重无须赘述。

代码如下：

 public class Solution {  
   /*  
    * @param numbers: Give an array numbers of n integer  
    * @return: Find all unique triplets in the array which gives the sum of zero.  
    */  
   public List<List<Integer>> threeSum(int[] numbers) {  
     // write your code here  
     List<List<Integer>> res = new ArrayList<>();  
     if(numbers == null || numbers.length < 3)  
       return res;  
     Arrays.sort(numbers);  
     for(int i = 0; i < numbers.length - 2; i++) {  
       if(i == 0 || (i > 0 && numbers[i] != numbers[i-1])) {  
         int left = i + 1;  
       int right = numbers.length - 1;  
       twoSum(numbers, res, -numbers[i], left, right);  
       }  
     }  
     return res;  
   }  
   private void twoSum(int[] nums,   
             List<List<Integer>> res,   
             int target,   
             int left,  
             int right) {  
     while(left < right) {  
       int sum = nums[left] + nums[right];  
       if(sum == target) {  
         List<Integer> cur = new ArrayList<>();  
         cur.add(-target);  
         cur.add(nums[left]);  
         cur.add(nums[right]);  
         res.add(cur);  
         right--;  
         left++;  
         while(left < right && nums[left] == nums[left-1]) {  
           left++;  
         }  
         while(left < right && nums[right] == nums[right+1]) {  
           right--;  
         }  
       } else if (sum < target) {  
         left++;  
       } else {  
         right--;  
       }  
     }  
     return;  
   }  
 }