LeetCode 15. 3Sum

Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

Source: https://leetcode.com/problems/3sum/

Solution

Note that the final result should not include duplicate triplets (compared by value).

The two-pointers solution for two-sum problem is a complete search for any approximations of target.

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 3) {
        return result;
    }

    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        // it is safe to skip duplicate first element
        // because for two identical first element,
        // the latter has a smaller selection range for its second and third elements
        if (i != 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // two sum
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == 0) {
                result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                // skip duplicate two sum combinations
                while (j < k && nums[j] == nums[j + 1]) {
                    j++;
                }
                while (j < k && nums[k] == nums[k - 1]) {
                    k--;
                }
                j++;
                k--;
            } else if (sum < 0) {
                j++;
            } else {
                k--;
            }
        }
    }
    return result;
}

public List<List<Integer>> threeSum2(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 3) {
        return result;
    }

    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        // it is safe to skip duplicate first element
        // because for two identical first element,
        // the latter has a smaller selection range for its second and third elements
        if (i != 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // two sum
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            // a better way to skip duplicates
            // can perform skipping even if sum != 0
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                j++;
                continue;
            }
            if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
                k--;
                continue;
            }

            int sum = nums[i] + nums[j] + nums[k];
            if (sum == 0) {
                result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                j++;
                k--;
            } else if (sum < 0) {
                j++;
            } else {
                k--;
            }
        }
    }
    return result;
}