三数之和

描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

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

输出：[[-1,-1,2],[-1,0,1]]

解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]

输出：[]

解释：唯一可能的三元组和不为 0 。

示例 3：

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

输出：[[0,0,0]]

解释：唯一可能的三元组和为 0 。

题解

暴力版

思路

三层循环，一个个加，如果和为0，则塞到数组里，最后再对结果进行去重，转为数字后输出

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum1 = (nums) => {
  const uniqueMap = new Set()
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        if (nums[i] + nums[j] + nums[k] === 0) {
          uniqueMap.add([nums[i], nums[j], nums[k]].sort().join('|'))
        }
      }
    }
  }
  return [...uniqueMap.keys()].map((item) => item.split('|').map((item) => Number(item)))
}

双指针+排序

思路

• 先对数组排序
• 对数组循环
• 如果当前下标 小于 数组长度-2 则终止
• 如果当前下标的值大于0，则终止
• 如果当前下标的值和上一个下标的值相同，则从下一个数字开始，去重
  • 创建左指针，指向当前下标+1的位置
  • 创建右指针，指向数组的末尾
  • 这里可以转为另外一个思路，计算左指针+右指针的值等于0-下标的值。但是这样后面还要去重一次
  • 计算当前下标的数字、左指针指向的数字、右指针指向的数字之和
    • 为0，则放到结果数组里，然后左右指针都移动一次
    • 大于0，说明大的值太大了，右指针向左移。移动之后检测当前的值是不是跟上一个值相同，相同则继续移动
    • 小于0，说明小的值太小了，左指针向右移。移动之后检测当前的值是不是跟上一个值相同，相同则继续移动
    • 循环上面这个，直到左指针等于右指针结束

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum2 = (nums) => {
  nums.sort((a, b) => a - b)
  const result = []
  const len = nums.length

  for (let i = 0; i < len - 2; i++) {
    if (nums[i] > 0) break
    if (nums[i] === nums[i - 1]) continue
    let left = i + 1
    let right = len - 1
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right]
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]])
        left++
        right--
        while (left < right && nums[left] === nums[left - 1]) {
          left++
        }
        while (left < right && nums[right] === nums[right + 1]) {
          right--
        }
      } else if (sum > 0) {
        right--
      } else {
        left++
      }
    }
  }
  return result
}