三数之和

排序+双指针

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b)

  const ans = []
  const n = nums.length

  for (let i = 0; i < n - 2; i++) {
    // 当前元素不等于上一个元素
    if (i > 0 && nums[i] == nums[i - 1]) continue

    // 优化
    if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break
    if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue

    let j = i + 1
    let k = n - 1

    while (j < k) {
      const sum = nums[i] + nums[j] + nums[k]

      if (sum > 0) {
        k--
      } else if (sum < 0) {
        j++
      } else {
        ans.push([nums[i], nums[j], nums[k]])

        j++
        while (j < k && nums[j] === nums[j - 1]) {
          j++
        }

        k--
        while (j < k && nums[k] === nums[k + 1]) {
          k--
        }
      }
    }
  }

  return ans
}