15. 三数之和-蒲公英云

15. 三数之和

题目描述：

给你一个包含 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 = []
输出：[]

示例 3：

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

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

题解：

方法一：暴力解法

题目中要求找到所有「不重复」且和为 0 的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下，数组中的元素全部为 0，即

[0, 0, 0, 0, 0, ..., 0, 0, 0]

任意一个三元组的和都为 0。如果我们直接使用三重循环枚举三元组，会得到 O(n3)个满足题目要求的三元组（其中 NN 是数组的长度）时间复杂度至少为 O(n3)。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此我们要换一种思路来考虑这个问题。

时间复杂度：O(n3)

方法二：排序 + 双指针

利用排序避免重复答案
利用双指针找到所有解

时间复杂度:

排序O(nLogn)

搜索解O(n2)

/* @param {number[]} nums @return {number[][]} /
var threeSum = function(nums) {
nums.sort((a, b) => a - b) // 升序

const result = []
const len = nums.length

for(let i = 0; i < len - 2; i ++) {

if(nums[i] === nums[i - 1]) {  // 有连续相同的值，直接跳过
  continue
}
let left = i + 1
let right = len - 1
while(left < right) { 
  let sum = nums[i] + nums[left] + nums[right]
  if(sum === 0) { 
    // 此处使用后++ --做双指针+-，因为此处等式成立，需同时给左指针+1，右指针-1
    result.push([nums[i], nums[left++], nums[right--]])
    while(nums[left] === nums[left - 1]) {  // 有连续相同的值，一样跳到下一个
      left ++
    }
    while(nums[right] === nums[right + 1]) {  // 有连续相同的值，跳到上一个
      right --
    }
  } else { 
    if(sum < 0) { 
      left ++
    } else { 
      right --
    }
  }
}