三数之和的简化版为 两数之和 。
图片.png

方法一：排序 + 双指针夹逼

  • 这道题的关键在于去重，而通过对 nums 进行排序，能高效地实现去重的操作，因为经过排序，重复的数字一定是临近的
  • 当确定了第一个数字的时候，其实就变成了 two sum 的问题，也就是 leetcode 的第一题。

思路：

  1. 通过遍历确定第一个数字
  2. 由于经过排序，数字是从小到大排列的，如果第一个数字都大于0，那么后面的数字无论如何想加，三数之和都不可能等于 0 的，这时候直接退出循环即可。
  3. 当确定了第一个数字之后，就转换成 two sum 问题，也就是 -a = b + c 的问题求解。我们以 a 的后一位作为 b 的初始位置，而已数组的最后一位作为 c 的初始位置。而求解 -a = b + c 的过程就是 b + c 不断逼近的过程。
    1. 如果 -a > b + c，由于 b 比 c 小，为了达到 -a = b + c，那么就应该增大 b，也就是将 b 向左移动。
    2. 如果 -a < b + c，由于 c 比 b 大，为了达到 -a = b + c，那么就应该减少 c，就是将 c 向右移动。
    3. 如果 -a = b + c，那么此时就已经找到 a + b + c = 0 的组合了。
  1. function threeSum(nums: number[]): number[][] {
  2.     const ans = []
  3.     const len = nums.length
  4.     if (len < 3) {
  5.         return ans
  6.     }
  8.     // 做升序处理
  9.     nums.sort((a, b) => a - b)
  11.     for (let i = 0; i < len - 2; i++) {
  12.         // 如果 i 大于 0，三数之和一定大于 0，直接退出 for 循环
  13.         if (nums[i] > 0) break
  15.         // 如果 i 与之前相同，则直接进入下一轮循环，避免重复
  16.         if (i > 0 && nums[i] === nums[i-1]) continue
  18.         let l = i + 1,
  19.             r = len - 1
  21.         while(l < r) {
  22.             const sum = nums[i] + nums[l] + nums[r]
  24.             if (sum === 0) {
  25.                 ans.push([nums[i], nums[l], nums[r]])
  26.                 // l 和 r 继续向中间逼近
  27.                 while(l < r && nums[l] === nums[l + 1]) l++
  28.                 while(l < r && nums[r] === nums[r - 1]) r--
  29.                 l++
  30.                 r--
  31.             } else if (sum < 0) {
  32.                 l++
  33.             } else if (sum > 0) {
  34.                 r--
  35.             }
  36.         }
  37.     }
  39.     return ans
  40. };
  • 时间复杂度 15. 三数之和 - 图2
  • 空间复杂度 15. 三数之和 - 图3