15-3sum

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

Дан массив целых чисел nums, верните все триплеты [nums[i], nums[j], nums[k]] такие, что i != j, i != k, и j != k, и nums[i] + nums[j] + nums[k] == 0. Набор решений не должен содержать дублирующихся триплетов. Вы можете вернуть результат в любом порядке. Ограничения: 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]))

Пример 1:
 
    Вход: nums = [-1,0,1,2,-1,-4]
    Выход: [[-1,-1,2],[-1,0,1]]
 
Пример 2:
 
    Вход: nums = [0,1,1]
    Выход: []
 
Пример 3:
 
    Вход: nums = [0,0,0]
    Выход: [[0,0,0]]

leetcode