第四题 三数之和

题目：

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

注意：

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

示例：

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

• 满足要求的三元组集合为：

  [
  [-1, 0, 1],
  [-1, -1, 2]
  ]

  思路一

• 三层遍历，三个指针

• 将三个和等于0的全部取出来，组成数组

  const numbs = [-1, 0, 1, 2, -1, -4]
  const add = function (numbs) {
  const arr = []
  for (let i = 0; i < numbs.length; i++) {
    for (let j = 1; j < numbs.length; j++) {
      for (let k = 2; k < numbs.length; k++) {
        if (numbs[i] + numbs[j] + numbs[k] === 0) {
          arr.push([numbs[i], numbs[j], numbs[k]])
        }
      }
    }
    break
  }
  return arr
  }
  console.log(add(numbs));

  问题：

• 有重复的

  思路二：

• 先排序，为了处理重复

• 循环遍历nums，因为排序了，所以当前数字大于0，之后的和一定大于0
• 当前不大于0，i每次遍历都会进行i++，每一项可能和前一项重复，如果重复跳出当前循环continue
• 如果不重复找出left和right做双指针，left是i后面每一项，right是从最后一项到前面每一项
• 然后遍历left不能大于等于right
• 求和：sum等于0，组装数据结构。然后还要去重，left和right的每一项不能重复。最后left++，right—
• 如果和小于0，我就让左边往后走一步
• 如果和大于0，我就让右边往后走一步

  const numbs = [-1, 0, 1, 2, -1, -4]
  const add = function (numbs) {
  const arr = []
  // 先排序 后续处理重复
  numbs = numbs.sort((a, b) => a - b)
  for (let i = 0; i < numbs.length; i++) {
    // 如果当前i与前一项相同，需要去重
    if (i > 0 && numbs[i] === numbs[i - 1]) continue;
    let left = i + 1
    let right = numbs.length - 1
    while (left < right) {
      const sum = numbs[i] + numbs[left] + numbs[right]
      if (sum === 0) {
        arr.push([numbs[i], numbs[left], numbs[right]])
        // 当前left与它后一项是否重复，重复就跳过计算，避免算出重复值
        while (left < right && numbs[left] === numbs[left + 1]) left++;
        // 当前right与前一项是否重复，重复跳过计算，避免算出重复值
        while (right < left && numbs[right] === numbs[right - 1]) right--;
        left++
        right--
      }
      // 如果和小于0，我就让左边往后走一步
      else if (sum < 0) left++;
      // 如果和大于0，我就让右边往后走一步
      else if (sum > 0) right--;
    }
  }
  return arr
  }
  console.log(add(numbs));