15-3sum

15. 3Sum (Medium) (https://leetcode.com/problems/3sum/)

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. The solution set must not contain duplicate triplets. You may return the output in any order. Constraints: 3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10

function threeSum(nums: number[]): number[][] {
  const triplets: number[][] = []
  nums.sort((a, b) => a - b);
 
  for (let i = 0; i < nums.length; i++) {
    let leftIdx = i + 1, rightIdx = nums.length - 1;
    if (i > 0 && nums[i] === nums[i - 1]) continue
 
    while (leftIdx < rightIdx) {
      const sm = nums[i] + nums[leftIdx] + nums[rightIdx]
 
      if (sm === 0) {
        triplets.push([nums[i], nums[leftIdx], nums[rightIdx]])
 
        leftIdx++
        rightIdx--
 
        // пропускаем одинаковые left значения
        while (
          leftIdx < rightIdx &&
          nums[leftIdx] === nums[leftIdx - 1]
        ) {
          leftIdx++
        }
 
        // пропускаем одинаковые right значения
        while (
          leftIdx < rightIdx &&
          nums[rightIdx] === nums[rightIdx + 1]
        ) {
          rightIdx--
        }
 
      } else if (sm > 0) {
        rightIdx--
      } else {
        leftIdx++
      }
    }
  }
 
  return triplets
}
 
// Local check:
console.log(threeSum([-1, 0, 1, 2, -1, -4]))
console.log(threeSum([0, 1, 1]))
console.log(threeSum([0, 0, 0]))

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

leetcode