三数之和 (opens new window)

• 难度：Medium
• 标签：排序 双指针

刷题思路

• [x] 排序+双指针夹逼
• [x] 排序+双指针夹逼(复用twoSum版本)

方法 1 排序+双指针夹逼

• 复杂度：
  • 时间 O(N^2). 排序 O(nlogn) + 遍历*左右指针的夹逼 O(n^2).
  • 空间 O(1)
• 结果：
  • 执行用时：148 ms, 在所有 JavaScript 提交中击败了97.64%的用户
  • 内存消耗：47.7 MB, 在所有 JavaScript 提交中击败了30.77%的用户

var threeSum = function(nums) {
    const res = []
    if (!nums || nums.length < 3) return res
    nums = nums.sort((a,b) => a-b)
    for (let i=0, len=nums.length; i<len && nums[i]<=0; i++) { // 最左值大于 0 时，后续已无解
        if (i>0 && nums[i]===nums[i-1]) continue // 重复则跳过
        let [left, right] = [i+1, len-1]
        while (left < right) {
            const tmp = nums[i] + nums[left] + nums[right]
            if (tmp === 0) {
                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--
                left++
                right--
            } else if (tmp < 0) {
                left++
            } else {
                right--
            }
        }
    }
    return res
};

方法 2 排序+双指针夹逼(复用twoSum版本)

• 复杂度：
  • 时间 O(N^2).同上
  • 空间 O(N) 计算 twoSum 时借助了与结果数量相同的额外空间，最好情况即无结果为, 最坏情况结果亦小于N, 故 O(N).
• 结果:
  • 执行用时：164 ms, 在所有 JavaScript 提交中击败了78.23%的用户
  • 内存消耗：48.3 MB, 在所有 JavaScript 提交中击败了12.34%的用户

var threeSum = function(nums) {
    if (!nums || nums.length<3) return []
    nums.sort((a,b) => a-b)
    const res = []
    for (let i=0, len=nums.length; i<len && nums[i]<=0; i++) {
        if (i>0 && nums[i]===nums[i-1]) continue
        const tmpArr = twoSum(nums, i+1, 0-nums[i])
        for (let j=0; j<tmpArr.length; j++) res.push([nums[i], ...tmpArr[j]])
    }
    return res
};

function twoSum (nums, start, target) {
    let [left, right] = [start, nums.length-1]
    const res = []
    while (left < right) {
        const tmp = nums[left] + nums[right]
        if (tmp === target) {
            res.push([nums[left], nums[right]])
            while (left<right && nums[left]===nums[left+1]) left++
            while (left<right && nums[right]===nums[right-1]) right--
            ;[left, right] = [left+1, right-1]
        } else if (tmp < target) {
            left++
        } else {
            right--
        }
    }
    return res
}

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~