Question

Given an array of n integers, are there elements a, b, c, 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] ]

Note

• 3 sum 問題逊谋，轉(zhuǎn)換成 two sum問題來解決盛霎。
• 對數(shù)組排序褐健，遍歷這個數(shù)組蝌矛，每獲取一個數(shù)脱羡，對數(shù)組剩余部分進行雙指針遍歷纵柿。

Extension

• 注意總結(jié) two sum 和 three sum 的解決問題思路明刷。three sum 問題是先固定一個數(shù)树瞭，然后使用 two sum 問題(HashMap拇厢，頭尾雙指針)來解。k sum問題可以通過遞歸最后使用 two sum 來解決晒喷。

Solution

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    if (nums == null || nums.length < 3) {
        return res;
    }
    int len = nums.length;
    Arrays.sort(nums);    // to sort the array.
    for (int i = 0; i < len - 2; i++) {    // len -2 is the end.
        if (i > 0 && nums[i] == nums[i-1]) {    // skip the duplicate elements.
            continue;
        }
        find(nums, i + 1, len - 1,  nums[i], res);
    }
    return res;
}

// two pointer solution.
private void find(int[] nums, int start, int end, int target, List<List<Integer>> res) {
    int l = start;
    int r = end;
    while (l < r) {
        if (nums[l] + nums[r] + target == 0) {
            List<Integer> item = new ArrayList<>();
            item.add(nums[l]);
            item.add(nums[r]);
            item.add(target);
            res.add(item);
            while (l < r && nums[l] == nums[l+1]) {   // skip left duplicate elements.
                l++;
            }
            while (l < r && nums[r] == nums[r-1]) {    // skip right duplicate elements.
                r--;
            }
            l++;
            r--;
        } else if (nums[l] + nums[r] + target < 0) {
            l++;
        } else {
            r--;
        }
    }
}