15. 3Sum

25 年 10 月 6 日 星期一
220 字
2 分钟
Screenshot 2025-10-06 at 12.06.53 am

核心思路:

枚举k,将i,j作为两数之和来做i,j分别为k+1和 n-1,记得命中之后去重,没有命中去重与否无所谓。如果 sum<0, 增大i,sum > 0减小j

优化:nums[k] > 0 break

js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 思路:枚举一个数当作target,剩下两个数做两数之和
var threeSum = function (nums) {
  const n = nums.length
  const ans = []
  nums.sort((a, b) => a - b)
  for (let k = 0; k < n; k++) {
    // 枚举k
    let i = k + 1,
      j = n - 1
    if (nums[k] === nums[k - 1]) continue
    while (i < j) {
      const s = nums[i] + nums[j] + nums[k]
      if (s === 0) {
        ans.push([nums[i], nums[j], nums[k]])
        i++
        j--
        // 命中后去重
        while (nums[i] === nums[i - 1]) i++
        while (j < n - 1 && nums[j] === nums[j + 1]) j--
      } else if (s < 0) {
        // s < 0 i增大 s增大
        i++
      } else j--
    }
  }
  return ans
}

文章标题:15. 3Sum

文章作者:Sirui Chen

文章链接:https://blog.siruichen.me/posts/15_3sum[复制]

最后修改时间:


商业转载请联系站长获得授权,非商业转载请注明本文出处及文章链接,您可以自由地在任何媒体以任何形式复制和分发作品,也可以修改和创作,但是分发衍生作品时必须采用相同的许可协议。
本文采用CC BY-NC-SA 4.0进行许可。