一天一大 leet(三数之和)难度:中等 DAY-12

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let end = nums.length,
    _result = []
  nums.sort((a, b) => a - b)
  if (nums.length < 3 || nums[end - 1] < 0) return []
  let secondMap = new Map()
  nums.some((first, i) => {
    if (first > 0) return true
    let second = i + 1
    let last = end - 1
    while (second < last) {
      if (first + nums[second] > 0) break
      let sum = first + nums[second] + nums[last]
      if (
        sum === 0 &&
        !(
          secondMap.has(nums[second] + '-' + nums[last]) ||
          secondMap.has(nums[last] + '-' + nums[second])
        )
      ) {
        _result.push([first, nums[second], nums[last]])
        secondMap.set(nums[second] + '-' + nums[last], second)
      }
      if (sum <= 0) {
        second++
      } else {
        last--
      }
    }
  })
  return _result
}

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

  // 枚举 a
  for (let first = 0; first < n; ++first) {
    // 需要和上一次枚举的数不相同
    if (first > 0 && nums[first] == nums[first - 1]) {
      continue
    }
    // c 对应的指针初始指向数组的最右端
    let third = n - 1
    let target = -nums[first]
    // 枚举 b
    for (let second = first + 1; second < n; ++second) {
      // 需要和上一次枚举的数不相同
      if (second > first + 1 && nums[second] == nums[second - 1]) {
        continue
      }
      // 需要保证 b 的指针在 c 的指针的左侧
      while (second < third && nums[second] + nums[third] > target) {
        --third
      }
      // 如果指针重合，随着 b 后续的增加
      // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
      if (second == third) {
        break
      }
      if (nums[second] + nums[third] == target) {
        _result.push([nums[first], nums[second], nums[third]])
      }
    }
  }
  return _result
}

const res = []
let numsLen = nums.length
if (numsLen < 3) return []

nums.sort((a, b) => a - b)
let lastNum = null
for (let i = 0; i < numsLen; i++) {
  if (nums[i] > 0) break
  if (nums[i] === lastNum) continue

  let L = i + 1
  let R = numsLen - 1
  while (L < R) {
    const sum = nums[i] + nums[L] + nums[R]
    if (sum === 0) {
      res.push([nums[i], nums[L], nums[R]])
      while (nums[L] === nums[L + 1]) L++
      while (nums[R] === nums[R - 1]) R--
      L++
      R--
    } else if (sum > 0) {
      R--
    } else {
      L++
    }
  }
  lastNum = nums[i]
}
return res

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b)
  const res = []
  for (let i = 0; i < nums.length - 2; i++) {
    let n1 = nums[i]
    if (n1 > 0) break
    if (n1 == nums[i - 1] && i > 0) continue // 遍历到重复的数，跳过
    let left = i + 1
    let right = nums.length - 1
    while (left < right) {
      let n2 = nums[left]
      let n3 = nums[right]
      if (n1 + n2 + n3 === 0) {
        res.push([n1, n2, n3])
        while (left < right && nums[left] === n2) left++ //直到指向不一样的数
        while (left < right && nums[right] === n3) right--
      } else if (n1 + n2 + n3 < 0) {
        left++
      } else {
        right--
      }
    }
  }
  return res
}