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重循環(huán)平匈。

• 外層循環(huán)遍歷數(shù)據(jù)隘膘，作為第一個(gè)數(shù)字脆丁，target – curNum作為2sum的target’樟蠕。
• 第一個(gè)數(shù)字如果大于0秕狰，則直接跳過族阅。 因?yàn)榕判蜻^后，遍歷時(shí)如果number大于0子眶，那么其后所有都大于0猫缭，不可能sum ==0

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

• 外層循環(huán)也需要去重復(fù)。同樣-3, -3, -2, -2, 0, 1, 2, 2, 3壹店，在外層循環(huán)的時(shí)候就要跳過第二個(gè)-3, -2 和2
  if (curIndex > 0 && number[curIndex] = number[curIndex - 1]) { continue;}
• 內(nèi)循環(huán)去重，需注意start和end都要進(jìn)行去重

參考代碼詳細(xì)備注

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++) {
            // 因?yàn)榕判蜻^后芝加，遍歷時(shí)如果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());

                    //需要去掉重復(fù)的元素藏杖，比如 -3, -2, -2, 0, 0, 5, 5. （-3為最外層循環(huán)将塑，那么TWO SUM已經(jīng)找到-2 ,5。 
                    // 此時(shí)需要去掉重復(fù)得-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;
        
    }
}