15. 3Sum.md

#15. 3Sum

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: 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]
]

思路：
找a+b+c = 0, 而abc可以重复出现在不同的小组合里，所以理论上需要三个index过三个array分别记录abc三个数。
在array a 里用i 做记录，固定i, 然后根据b array 中每一个j, 检查c array. 这样就是N^3 的时间，
保证每一个组合都没漏掉。
实际操作的时候，用array排序略微简化了一点，用sum 的正负决定到底是移动j 还是k.
时间复杂度n^2.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;


public List<List<Integer>> threeSum(int[] nums) {
	Arrays.sort(nums);
    List<List<Integer>> result = 
    			new ArrayList<>();
    	
    for (int i = 0; i < nums.length-2; i++){
    	int j = i+1;
    	int k = nums.length -1;
    		
    	while (j <k){
    		int sum = nums[i] + nums[j] + nums[k];
    			
    		if (sum < 0) j++;
    		else if (sum == 0){
    			Integer[] arr = new Integer[] 
    					{nums[i], nums[j], nums[k]};
    			result.add(new ArrayList<Integer>(Arrays.asList(arr)));

    			//相邻两个数如果一样的话，跳过去。
    			do {j++;} while (j < k && nums[j] == nums[j-1]);
    			do {k--;} while (j < k && nums[k] == nums[k+1]); 
    			}
    		else k--;
    		}
    		//跳过去，避免重复。
    		while ( i< nums.length -1 && nums[i] == nums [i+1])
    			i++;
    	}
    	
    	return result;
    }