LeetCode-15.三数之和

题目详解

相关链接

• 代码随想录

思路

之前做过的忘了。。。

看完代码随想录之后的想法

• 巧用双指针，看完视频后对去重细节理解了，自己写就一遍过了

实现过程中遇到的困难

• 对第一个数去重
• 对后两个数去重

代码

TypeScript

function threeSum(nums: number[]): number[][] {
  const len = nums.length;
  if (len < 3) return []
  const res: number[][] = []
  nums.sort((a, b) => a - b)
  for (let i = 0; i < len - 2; i++) {
    if (nums[i] > 0) break // 剪枝
    if (i > 0 && nums[i] === nums[i - 1]) continue // 去重
    let left = i + 1,
      right = len - 1
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right]
      if (sum < 0) left++
      else if (sum > 0) right--
      else {
        res.push([nums[i], nums[left++], nums[right--]])
        while (left < right && nums[left] === nums[left - 1]) left++ // 去重
        while (left < right && nums[right] === nums[right + 1]) right-- // 去重
      }
    }
  }
  return res
}

时间复杂度：O(n^2)
空间复杂度：O(n)

收获