15.三数之和

发表于 分类于 阅读次数：

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

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

示例 1：

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

1
2
输入：nums = []
输出：[]

示例 3：

1
2
输入：nums = [0]
输出：[]

暴力破解法:

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let arr = nums.sort((a, b) => a - b);
  let zeroIndex = arr.findIndex((e) => e >= 0);
  let minus = [];
  let plus = [];
  minus = arr.slice(0, zeroIndex);
  plus = arr.slice(zeroIndex + 1, arr.length);
  if (arr[zeroIndex] === 0) {
    minus.push(0);
  } else {
    plus.unshift(arr[zeroIndex]);
  }
  let result = {};
  for (let i = 0; i < minus.length; i++) {
    for (let j = i + 1; j < minus.length; j++) {
      let add = (minus[i] + minus[j]) * -1;
      if (plus.indexOf(add) !== -1) {
        result[`${minus[i]},${minus[j]},${add}`] = true;
      }
    }
  }
  for (let i = 0; i < plus.length; i++) {
    for (let j = i + 1; j < plus.length; j++) {
      let add = (plus[i] + plus[j]) * -1;
      if (minus.indexOf(add) !== -1) {
        result[`${add},${plus[i]},${plus[j]}`] = true;
      }
    }
  }
  return Object.keys(result).map((item) => item.split(","));
};

运行结果：

1
2
3
4
执行结果：通过

执行用时：6520 ms, 在所有 JavaScript 提交中击败了5.02%的用户
内存消耗：52 MB, 在所有 JavaScript 提交中击败了5.02%的用户

一顿操作猛如虎，击败用户百分五。看了题解有了下面的代码：

排序+双指针：

思路

  • 数组遍历
  • 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L]和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
  • 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
  • 如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
  • 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
  • 当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R–
  • 时间复杂度：O(n^2)，n 为数组长度
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
var threeSum = function (nums) {
  let result = [];
  const len = nums.length;
  if (nums == null || len < 3) return result;
  nums.sort((a, b) => a - b);

  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) break; // 结束循环
    if (nums[i] === nums[i - 1]) continue; // 去重
    let L = i + 1;
    let R = len - 1;

    while (L < R) {
      let sum = nums[i] + nums[L] + nums[R];
      if (sum === 0) {
        result.push([nums[L], nums[i], nums[R]]);
        while (L < R && nums[L] == nums[L + 1]) L++; // 去重
        while (L < R && nums[R] == nums[R - 1]) R--; // 去重
        L++;
        R--;
      } else if (sum < 0) {
        L++;
      } else {
        R--;
      }
    }
  }
  return result;
};