15.三数之和.md

LeetCode-15 三数之和

难度： 中等

类型： 数组

题目：

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路：

第一反应是想用双指针去实现(也叫双指针碰撞法)。

1. 用双指针去实现的话，首先第一步得先排序，这样前后两个指针移动的时候，才能知道我们要具体移动哪个指针。

 nums = nums.sort((a, b) => a - b)

2. 排完序后，就要思考怎么去进行对比？ 可以选择一个基数保持不变，然后通过左指针和右指针去移动，判断 基数+左指针指向的数+右指针指向的数 === 0 。

3. 接下来就要去循环nums数组,并且创建左右两个指针。

// 缓存数组的length
let len = nums.length

// 准备一个存放结果的数组
let res = []

// 思考： 这里为什么只循环到 len - 2?
for (let i = 0; i < len - 2; i++) {
  // 那么每次循环的时候，这个基数就是 i,每次那这个基数i和左右两个指针指向的数去相加，看是否为0

  // 定义 左指针 和 有 右指针
  // 左指针指向基数后一个，右指针从最后一个开始，所以上面循环的条件是循环到倒数第三个数就结束了，因为j指向倒数第二个数，k会指向倒数第一个数
  let j = i + 1, k = len - 1

  // 当两个指针相遇的时候 j >=k, 停止循环
  while (j < k) {
    // dosomething...
  }

}

4. 在while循环的过程中，三数相加，会出现三种情况：
   • 相加小于0 （nums[i] + nums[j] + nums[k] < 0）, 说明左指针指向的数小了，需要往后移动左指针。（因为基数在一次循环中是不变的，可以看为一个不变的常量，只需要判断左指针和右指针移动哪个。此时nums[j] < nums[k], 而我们的目的是要尽可能让三数相加等于0，所以此时需要往后移动左指针，让nums[j]大点）。
     • 特殊情况：如果左指针j往后移动了一个数，发现这个数和前一个左指针指向的数相同，那么此时左指针应该略过这个数，继续向后移动。

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

• 相加大于0 （nums[i] + nums[j] + nums[k] > 0）, 说明右指针指向的数大了，需要往前移动右指针，让其数值变小。（还是将nums[i]看作一个常量， 并且nums[j]始终是小于nums[k]的，为了尽可能让三数相加等于0，需要往前移动右指针，让nums[k]小点）。
  • 特殊情况：如果右指针往前移动了一个数，发现这个数和前以一个右指针指向的数相同，那么此时右指针应该略过这个数，继续向前移动。

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

• 相加等于0（nuns[i] + nums[j] + nums[k] === 0）,则就将 nums[i], nums[j], nums[k] 放入数组，并推入到结果res中去。并且左指针j和右指针k继续移动。
• 特殊情况： 如果左右指针移动的过程中，还是发现当前指针和之前指针指向的数相同，继续略过这个数，然后再继续移动指针。

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

5. 上面步骤一直判断的是内层循环的过程中，左右两个指针的移动方向和遇到指针移动的过程中，遇到相同元素的处理。那么在外层循环中，每次改变的是基数，在基数变化的过程中，也可能会遇到当前基数与之前的基数相同的情况，那么此时循环也应该跳过（前后两个基数相同，那么在前一个基数循环的过程中，两个指针移动的过程中就已经比对过了，没必要再进行一次，节省时间），继续找下一个基数。

  for (let i = 0; i < len - 2; i++) {
    if (i > 0 && nums[i] === nums[i-1]) {
      continue
    }
  }

实现：

javascript:

时间复杂度: O(n^2)

空间复杂度：O(1)

function threeSum(nums) {
  nums = nums.sort((a, b) => a - b)
  
  let len = nums.length

  let res = []

  for (let i = 0; i < len - 2; i++) {
    let j = i + 1, k = len - 1

    if (i > 0 && nums[i] === nums[i-1]) {
      continue
    }

    while (j < k) {
      if (nums[i] + nums[j] + nums[k] < 0) {
        j++
        while (j < k && nums[j] === nums[j-1]) {
          j++
        }
      } else if (nums[i] + nums[j] + nums[k] > 0) {
        k--
        while (j < k && nums[k] === nums[k+1]) {
          k--
        }
      } else {
        res.push([nums[i], nums[j], nums[k]])
          j++
          k--
        while (j < k && nums[j] === nums[j-1]) {
          j++
        }
        while (j < k && nums[k] === nums[k+1]) {
          k--
        }
      }
    }
  }
  return res
}