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

思路

和用双指针的2SUM一样，只是用2重循环。

• 外层循环遍历数据，作为第一个数字，target – curNum作为2sum的target’。
• 第一个数字如果大于0，则直接跳过。 因为排序过后，遍历时如果number大于0，那么其后所有都大于0，不可能sum ==0

            if (numbers[i] > 0) {
                break;
            }

• 外层循环也需要去重复。同样-3, -3, -2, -2, 0, 1, 2, 2, 3，在外层循环的时候就要跳过第二个-3, -2 和2
  if (curIndex > 0 && number[curIndex] = number[curIndex - 1]) { continue;}
• 内循环去重，需注意start和end都要进行去重

参考代码详细备注

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>> result = new ArrayList<>();
        
        if (numbers == null && numbers.length < 3) {
            return result;
        }
        
        Arrays.sort(numbers);
        
        for (int i = 0; i < numbers.length - 2; i++) {
            // 因为排序过后，遍历时如果number大于0，那么其后所有都大于0，不可能sum ==0
            if (numbers[i] > 0) {
                break;
            }
            
            if (i > 0 && numbers[i] == numbers[i - 1]) {
                continue;
            }
            
            int head = i + 1;
            int tail = numbers.length - 1;
            int target = 0 - numbers[i];
            
            //TWO SUM
            while (head < tail) {
                if (numbers[head] + numbers[tail] > target) {
                    tail--;
                } else if (numbers[head] + numbers[tail] < target) {
                    head++;
                } else {
                    result.add(Arrays.asList(numbers[i], numbers[head], numbers[tail]));
                                System.out.print(result.toString());

                    //需要去掉重复的元素，比如 -3, -2, -2, 0, 0, 5, 5. （-3为最外层循环，那么TWO SUM已经找到-2 ,5。 
                    // 此时需要去掉重复得-2 和 5
                    
                    //remove duplicate from the left
                    while (++head < tail && numbers[head] == numbers[head - 1]) {
                        continue;
                    }
                    //remove duplicate from the right
                    while (--tail > head && numbers[tail] == numbers[tail + 1]) {
                        continue;
                    }
                }
            }
            
        }
        return result;
        
    }
}