three sum

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 问题，转换成 two sum问题来解决。
• 对数组排序，遍历这个数组，每获取一个数，对数组剩余部分进行双指针遍历。

Extension

• 注意总结 two sum 和 three sum 的解决问题思路。three sum 问题是先固定一个数，然后使用 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--;
        }
    }
}