16. 3Sum

MediumArray Two Pointers Sorting

Given an integer array nums, return every distinct triplet of values [a, b, c] taken from three different positions i, j, k of the array such that a + b + c == 0.

Two triplets are the same if they contain the same values, so the result must not contain duplicates. The triplets may be returned in any order, and so may the values inside each triplet.

Example 1

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

Explanation: -2 + 1 + 1 = 0 uses both 1s. [-1,0,1] can be built with either of the two 1s, but it is listed only once.

Example 2

Input: nums = [3,-1,5]
Output: []

Explanation: The only triplet sums to 7.

Example 3

Input: nums = [0,0,0,0]
Output: [[0,0,0]]

Explanation: Several index choices give [0,0,0], but it is reported once.

Constraints

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

💡 Hint 1

Checking every triple is O(n³). If you fix the first value a, what problem is left for the other two?

💡 Hint 2

After sorting, "find two values summing to -a" can be solved with two pointers moving towards each other.

💡 Hint 3

To avoid duplicate triplets, skip over equal neighbours: for the fixed value and for each pointer after a match.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Sort the array, then fix the smallest value nums[i] of the triplet. The other two must sum to -nums[i] and lie to the right of i, so run two pointers lo = i + 1 and hi = n - 1: if the sum is too small move lo right, if too large move hi left, and on a match record it and move both. Duplicates are avoided by skipping a fixed value equal to the previous one, and by stepping lo past equal values after a match. Once nums[i] > 0 no triplet can sum to zero, so you can stop.

Time O(n²)Space O(1) extra besides sorting and the output

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let lo = i + 1;
    let hi = nums.length - 1;
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (sum < 0) lo++;
      else if (sum > 0) hi--;
      else {
        result.push([nums[i], nums[lo], nums[hi]]);
        lo++;
        hi--;
        while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
      }
    }
  }
  return result;
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum < 0) lo++;
                else if (sum > 0) hi--;
                else {
                    result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    lo++;
                    hi--;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                }
            }
        }
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit