题目描述

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

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

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

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

解法

解法一（暴力掉头发法）

思路：

对数组进行三层遍历，通过三个游标，找到所有满足 a + b +c = 0的结果。
然后对结果进行去重，剔除重复的三元组。

缺点：

在leetcode执行，由于执行时间过长而失败。

var threeSum = function(nums) {
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    const a = nums[i];

    for (let j = i + 1; j < nums.length - 1; j++) {
      const b = nums[j];
      
      for (let z = j + 1; z < nums.length; z++) {
        const c = nums[z];
        if (a + b + c === 0) {
          result.push([a, b, c].sort((a,b) => a-b));
        }
      }
    }
    
  }

  if (result.length === 0) return [];

  const copy_result = result.slice(0);
  for (let t = 0; t < result.length; t++) {
    const temp_a = result[t];

    for (let tx = t + 1; tx < result.length; tx++) {
      const temp_b = result[tx];
      
      if (temp_b.every((value, index) => value === temp_a[index])) {
        delete copy_result[tx];
      }
    }
  }

  return copy_result.filter((value) => value != null);
};

解法二（推荐）

思路：

将数组排序
定义3个指针 i, j, k，遍历元素i，找到使 nums[j] + nums[k] = -nums[i] 等式成立的结果集。这样，就能将三数之和的问题转化为两数之和的问题。

详细思路可以看老表同学的笔记，其中最有趣的是第二步的搜索过程，用到了双指针夹逼搜索，并且做了相同元素过滤处理：

老表同学的笔记

var threeSum = function(nums) {
  const result = [];
  nums.sort((a,b) => a - b);

  for (let i = 0; i < nums.length; i++) {
    if (i==0 || nums[i] > nums[i -1]) {
      let j = i +1;
      let k = nums.length - 1;

      while (j < k) {
        const sum = nums[i] + nums[j] + nums[k];
        if (sum === 0) {
          result.push([ nums[i], nums[j], nums[k] ]);

          j++;
          k--;
          
          // 剔除相同参数
          while (j<k && nums[j] === nums[j - 1]) {
            j++;
          }
          
          // 剔除相同参数
          while (k > j && nums[k] === nums[k+1]) {
            k--;
          }
        } else if (sum > 0) {
          k--;
        } else if (sum < 0) {
          j++;
        }
      }
    }
  }

  return result;
};

时间复杂度：小于 O(n^2)
与方法一相比，执行速度非常快，而且效率高。