3Sum (sort + two pointers)

Medium TimeO(n²) SpaceO(1) extra

Given an array nums of integers, return every distinct triple of values that adds up to zero — for [-1, 0, 1, 2, -1, -4] those are [-1, -1, 2] and [-1, 0, 1]. The three values must come from three different positions, triples count as the same when their values match however many positions could have produced them, and the order of the triples in the result does not matter.

Examples

Example 1

Input
nums = [-1, 0, 1, 2, -1, -4]
Output
[[-1,-1,2],[-1,0,1]]
-1 + -1 + 2 = 0 and -1 + 0 + 1 = 0; the two -1s are different positions.

Example 2

Input
nums = [0, 0, 0, 0]
Output
[[0,0,0]]
Four zeros give 0 + 0 + 0 = 0 four ways over, but as values that is one triple.

The Code

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}
threeSum([-1, 0, 1, 2, -1, -4]);
Done
Step through threeSum([-1, 0, 1, 2, -1, -4]) call by call

More like this

All two pointers examples (9) →