给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

思路

  1. 先排序，i 从小到大遍历，对应的 j、k 由两端往中间移动，时间复杂度 O(n^2)
  2. 遍历时 i, j, k 需要 “去重” 以避免产生相同的结果三元组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var threeSum = function (nums) {
  nums.sort((a, b) => a - b)
  const target = 0
  const result = []
  for (let i = 0; i < nums.length - 2; ++i) {
    const iVal = nums[i]
    // 避免输出重复结果元组
    if (i > 0 && iVal === nums[i - 1]) {
      continue
    }
    let j = i + 1
    let k = nums.length - 1
    while (j < k) {
      const jVal = nums[j]
      const kVal = nums[k]
      const sum = iVal + jVal + kVal
      if (sum < target) {
        ++j
      } else if (sum > target) {
        --k
      } else {
        result.push([iVal, jVal, kVal])

        // 避免输出重复结果元组
        while (j < k && nums[j] === jVal) {
          ++j
        }
        while (j < k && nums[k] === kVal) {
          --k
        }
      }
    }
  }
  return result
}