题目描述

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

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

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

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

来源：LeetCode

思路

这题拿到首先想到的是深搜+去重， 结果就是超时。然后无论怎么剪枝还是超时。

不得不完全换一种方法。

先将数组排序。

用 三 个指针去寻找和为 0 的组合。stable为固定指针，固定在左侧。然后用left和right两指针分别放在stable右侧子数组的两侧，然后向中移动，寻找可能的组合。
移动时要分情况处理：

  1. 若组合大于 0，需要调小，则把 right 向左移动。为避免得到重复组合，需要越过相同的值。
  2. 若组合小于 0，需要调大，则把 left 向右移动。同样越过相同的值。
  3. 若组合等于 0，就得到一个有效组合。此时再单独移动 left 或 right 都不会再得到 0，所以 left 和 right 都需要向中移动。

当 left 与 right 相遇时，结束本轮。

然后将 stable 右移，注意越过相同值，继续搜索。

解法

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

  // 移动
  const move = (index, step) => {
    let newIndex = index + step;

    while (nums[newIndex] === nums[index]) {
      newIndex += step;
    }

    return newIndex;
  };

  let stable = 0;

  while (nums[stable] <= 0 || stable <= nums.length - 3) {
    let left = stable + 1;
    let right = nums.length - 1;

    while (left < right) {
      if (nums[stable] + nums[left] + nums[right] === 0) {
        result.push([nums[stable], nums[left], nums[right]]);

        left = move(left, 1);
        right = move(right, -1);
      } else if (nums[stable] + nums[left] + nums[right] < 0) {
        left = move(left, 1);
      } else {
        right = move(right, -1);
      }
    }

    stable = move(stable, 1);
  }

  return result;
};
Last Updated:
Contributors: henri.zhang