三数之和

力扣🔗：https://leetcode-cn.com/problems/3sum (opens new window)

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = [0]
输出：[]

提示：

• 0 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

解题思路

• 首先进行过滤，当传入数组 nums 长度小于 3 时，返回结果 []。

• 然后将 nums 由小到大进行排序，随后判断第一个数是否大于 0 或最后一个数小于 0，若满足条件则证明不可能有三数之和等于 0，返回结果 []。

• 从左往右依次遍历 nums 中每个值，记录索引值为 base，直到 nums[base] 大于 0。若 nums[base] === num[base - 1]，则跳过当前循环。

• 在每个循环体中，nums[base] 作为固定的加数，设置左指针 left 和右指针 right，初始值分别为 base + 1 和 nums.length - 1，变量 sum 表示当前循环中的三数之和 nums[base] + nums[left] + nums[right]。根据以下情况移动双指针：

  • 当 sum < 0，表示左边两数之和较小，因此向右移动左指针。
  • 当 sum > 0，表示左边两数之和较大，因此向左移动右指针。
  • 当 sum === 0 时，如果左右指针指向的下一个值与当前指向值相等，则继续往下一个值移动，直到不相等。

代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
  const result = []
  const l = nums.length
  if (l < 3) return result

  nums.sort((a, b) => a - b) // 由小到大对数组进行排序
  if (nums[0] > 0 || nums[l - 1] < 0) return result // 如果第一个数大于 0 或最后一个数小于 0，则不可能有三数之和等于 0 

  for (let base = 0; base < l; base++) {
    // 从左至右遍历数组，直到当前值大于 0
    if (nums[base] === nums[base - 1]) continue // 如果与上一个值相同，跳过当前值
    if (nums[base] > 0) return result
    let left = base + 1 // 左指针
    let right = l - 1 // 右指针

    while (left < right) {
      // 每循环一次，当前的 nums[base] 作为不变的加数，移动双指针寻找符合条件的值
      const sum = nums[base] + nums[left] + nums[right]

      if (sum === 0) {
        // 三数之和等于 0 时
        result.push([nums[base], nums[left], nums[right]])

        while (left < right && nums[left] === nums[left + 1]) {
          // 当左指针指向的值与它右边的值相等时，向右移动左指针
          left++
        }

        while (right > left && nums[right] === nums[right - 1]) {
          // 当右指针指向的值与它左边的值相等时，向左移动右指针
          right--
        }

        left++ // 向右移动左指针
        right-- // 向左移动右指针
      } else {
        // 三数之和小于 0 时，向右移动左指针
        // 三数之和大于 0 时，向左移动右指针
        sum < 0 ? left++ : right--
      }
    }
  }
}