15. 3Sum

Problem:

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

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

To simplify the problem, sort the nums first.

If sorted[0] > 0 or sorted[last] < 0, return an empty set.

From i = 0 to len(sorted) - 2, pick sorted[i] as the first number of a possible triplet result.

Let l = i + 1, r = len(sorted) - 1, we want to narrow them down to enumerate all possible combinations.

• l++ if sorted[i] + sorted[l] + sorted[r] > 0.
• r-- if sorted[i] + sorted[l] + sorted[r] < 0.

Skip any duplicate number as we iterate to avoid duplicate triplets.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let threeSum = function (nums) {
  const len = nums.length
  const sorted = nums.sort((a, b) => a - b)
  const result = []

  if (sorted[0] > 0 || sorted[len-1] < 0) {
    return result
  }

  for (let i = 0; i < len - 2; i++) {
    if (sorted[i] > 0) {
      break
    }

    if (i > 0 && sorted[i] === sorted[i-1]) {
      continue
    }

    const twoSum = 0 - sorted[i]

    for (let l = i + 1, r = len - 1; l < r;) {
      const diff = twoSum - sorted[l] - sorted[r]
      if (diff > 0) {
        l++
      } else if (diff < 0) {
        r--
      } else {
        result.push([sorted[i], sorted[l], sorted[r]])
        while (++l < r && sorted[l] === sorted[l - 1]);
        while (--r > l && sorted[r] === sorted[r + 1]);
      }
    }
  }

  return result
};