15、三数之和

;(function () {
  /**
   * 15. 三数之和
   * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
   * 注意：答案中不可以包含重复的三元组。
   *
   * 输入：nums = [-1,0,1,2,-1,-4]
   * 输出：[[-1,-1,2],[-1,0,1]]
   *
   * 输入：nums = []
   * 输出：[]
   *
   * 输入：nums = [0]
   * 输出：[]
   *
   */

  function threeSum(nums: number[]): number[][] {
    // 方法一：暴力循环 --- 超出时间限制
    // let set = new Set();
    // let res: number[][] = [];
    // for (let i = 0; i < nums.length; i++) {
    //     // a
    //     for (let j = i + 1; j < nums.length; j++) {
    //         // b
    //         for (let k = j + 1; k < nums.length; k++) {
    //             // c
    //             if (nums[i] + nums[j] + nums[k] === 0) {
    //                 let sortArr = [nums[i], nums[j], nums[k]].sort((a: number, b: number) => a - b);
    //                 let sortArrStr = sortArr.join('-')
    //                 if (!set.has(sortArrStr)) {
    //                     res.push(sortArr)
    //                     set.add(sortArrStr)
    //                 }
    //             }
    //         }
    //     }
    // }
    // return res

    // 方法二：
    // 1. 排序；2. 双指针
    let ans: number[][] = []
    const len = nums.length
    if (nums === null || len < 3) return ans
    // 排序
    nums.sort((a: number, b: number) => a - b)
    for (let i = 0; i < len; i++) {
      // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
      if (nums[i] > 0) break
      // 去重
      if (i > 0 && nums[i] === nums[i - 1]) continue
      let L = i + 1
      let R = len - 1
      while (L < R) {
        const sum = nums[i] + nums[L] + nums[R]
        if (sum === 0) {
          ans.push([nums[i], nums[L], nums[R]])
          // 去重
          while (L < R && nums[L] === nums[L + 1]) L++
          while (L < R && nums[R] === nums[R - 1]) R--
          L++
          R--
        } else if (sum < 0) {
          L++
        } else if (sum > 0) {
          R--
        }
      }
    }
    return ans
  }

  console.log(threeSum([-1, 0, 1, 2, -1, -4]))
})()