15. 3Sum

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 思路：枚举一个数当作target，剩下两个数做两数之和()
var threeSum = function (nums) {
  // 1. 对数组进行升序排序
  // 排序是双指针法的基础，也便于后续去重和提前终止循环
  nums.sort((a, b) => a - b)

  // 获取数组长度，避免重复计算
  const n = nums.length

  // 用于存储最终满足条件的三元组结果
  const ans = []

  // 2. 固定第一个数 nums[i]，遍历数组（i最多到n-3，因为需要留j和k两个位置）
  for (let i = 0; i < n - 2; i++) {
    // 当前固定的第一个数
    const x = nums[i]

    // 去重：如果当前数和前一个数相同，跳过（避免重复的三元组）
    // i > 0 是为了防止 i-1 越界
    if (i > 0 && x === nums[i - 1]) continue

    // 优化一：提前终止循环
    // 如果当前最小的三个数之和（x + nums[i+1] + nums[i+2]）都大于0，
    // 那么后续更大的数组合也不可能等于0，直接终止整个循环
    if (x + nums[i + 1] + nums[i + 2] > 0) break

    // 优化二：跳过当前i的循环
    // 如果当前数和最大的两个数之和（x + nums[n-2] + nums[n-1]）都小于0，
    // 那么当前i不可能找到符合条件的j和k，直接进入下一个i的循环
    if (x + nums[n - 2] + nums[n - 1] < 0) continue

    // 3. 双指针法：j 从i+1开始（第二个数），k从数组末尾开始（第三个数）
    let j = i + 1,
      k = n - 1

    // 双指针遍历，j < k 保证两个指针不重叠
    while (j < k) {
      // 计算三个数的和
      const s = x + nums[j] + nums[k]

      if (s > 0) {
        // 和大于0：需要减小和，k指针左移（数组已排序，左边数更小）
        k--
      } else if (s < 0) {
        // 和小于0：需要增大和，j指针右移（数组已排序，右边数更大）
        j++
      } else {
        // 4. 找到满足条件的三元组：和等于0
        ans.push([x, nums[j], nums[k]])

        // 去重：跳过j指针指向的重复数字
        // j++ 先移动指针，然后判断是否和前一个数相同，且保证j < k
        for (j++; j < k && nums[j] === nums[j - 1]; j++);

        // 去重：跳过k指针指向的重复数字
        // k-- 先移动指针，然后判断是否和后一个数相同，且保证k > j
        for (k--; k > j && nums[k] === nums[k + 1]; k--);
      }
    }
  }

  // 返回所有满足条件的不重复三元组
  return ans
}

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