3Sum

Description

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.

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

Solution(javascript)

// /** Binary Search O(N^2(logN))
//  * @param {number[]} nums
//  * @return {number[][]}
//  */
// const threeSum = function (nums) {
//   nums.sort((a, b) => a - b)
//   const search = (left, right, target) => {
//     while (left <= right) {
//       const middle = left + Math.floor((right - left) / 2)
//       if (nums[middle] === target) {
//         return middle
//       } if (nums[middle] < target) {
//         left = middle + 1
//       } else {
//         right = middle - 1
//       }
//     }
//     return -1
//   }
//   const result = []
//   for (let i = 0; i < nums.length; i++) {
//     if (nums[i] === nums[i - 1]) {
//       continue
//     }
//     for (let j = i + 1; j < nums.length; j++) {
//       if (j > i + 1 && nums[j] === nums[j - 1]) {
//         continue
//       }
//       const index = search(j + 1, nums.length - 1, -(nums[i] + nums[j]))
//       if (index >= j + 1) {
//         result.push([nums[i], nums[j], nums[index]])
//       }
//     }
//   }
//   return result
// }

/** Two Pointers O(N^2)
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = function (nums) {
  nums.sort((a, b) => a - b)
  const result = []
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) {
      continue
    }
    let left = i + 1
    let right = nums.length - 1
    while (left < right) {
      if (left > i + 1 && nums[left] === nums[left - 1]) {
        left += 1
        continue
      }
      const sum = nums[left] + nums[right] + nums[i]
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]])
        left += 1
        right -= 1
      } else if (sum > 0) {
        right -= 1
      } else {
        left += 1
      }
    }
  }
  return result
}