原题：三数之和

思路：排序后头尾双指针向中间移动

这题是我永远滴痛，在没任何算法基础的时候有一家心仪的公司就挂在这题的变体！！

思路

这种找边界组合的问题，一般通过排序 + 双指针就能解决，这题就是非常经典的一道题

这题要求的是三数和为 0 即 a + b + c = 0，稍微理解下技能明白，求 a 固定时 b 和 c 的不同组合，就能解决这道题

1. 排序

从小到大排序，这边为了方便我们直接用库函数就行

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

2. 开始遍历每一个数字

  1. 若当前数字大于 0，因为是升序，右边的数只会更大，结果必定大于 0，直接返回结果
1
if (nums[i] > 0) return result;
  1. 如果当前下标大于 0 且当前数与上一数相同，跳过，避免重复解 i > 0 && nums[i] === nums[i - 1]
1
if (i > 0 && nums[i] === nums[i - 1]) continue;
  1. 定义指针 L 指向下一个数 i + 1，指针 R 指向数组尾部 nums.length - 1
1
2
var L = i + 1;
var R = nums.length - 1;

3. 移动两指针直到相遇

  1. 如果和为 0，推入结果，跳过两侧指针相同的值
1
2
3
4
5
6
7
if (nums[i] + nums[L] + nums[R] === 0) {
  result.push([nums[i], nums[L], nums[R]]);
  while (L < R && nums[L] === nums[L + 1]) L++;
  while (L < R && nums[R] === nums[R - 1]) R--;
  L++;
  R--;
}
  1. 如果和大于 0，则需要更小的值，右侧指针移动 R--
1
else if (nums[i] + nums[L] + nums[R] > 0) R--;
  1. 如果和小于 0，则需要更大的值，左侧指针移动 L++
1
else L++;

4. 跳出两个循环后

直接返回结果

完整代码

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const result = [];
  nums = nums.sort((a, b) => a - b);
  for (var i = 0; i < nums.length; i++) {
    // 大于 0 说明右侧的数加上  num[i] 必定大于 0
    if (nums[i] > 0) return result;
    // 如果当前数与上一数相同，跳过避免重复解
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    var L = i + 1;
    var R = nums.length - 1;
    while (L < R) {
      if (nums[i] + nums[L] + nums[R] === 0) {
        // 如果等于 0，加入结果，并跳过后面的重复解
        result.push([nums[i], nums[L], nums[R]]);
        while (L < R && nums[L] === nums[L + 1]) L++;
        while (L < R && nums[R] === nums[R - 1]) R--;
        L++;
        R--;
        // 大于 0，需要更小的值，右侧指针向左移动
      } else if (nums[i] + nums[L] + nums[R] > 0) R--;
      // 小于 0，需要更大的值，左侧指针向右移动
      else L++;
    }
  }
  return result;
};