# 四数之和 (opens new window)

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

# 刷题思路

[x] 排序+双指针夹逼(复用twoSum版本)
[x] 排序+双指针夹逼(复用twoSum版本 & 加入剪枝)

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

思路:
- 复用：套用 threeSum 的解题方式，即复用其 twoSum 解题模板
复杂度：
- 时间 O(n^3). 排序 O(nlogn) + 遍历*左右指针的夹逼 O(n^3).
- 空间 O(n) 计算 twoSum 时借助了与结果数量相同的额外空间，最好情况即无结果为, 最坏情况结果亦小于N, 故 O(n).
结果：
- 执行用时：132 ms, 在所有 JavaScript 提交中击败了33.14%的用户
- 内存消耗：39.9 MB, 在所有 JavaScript 提交中击败了25.47%的用户

var fourSum = function(nums, target) {
    if (!nums || nums.length<4) return []
    nums.sort((a, b) => a-b)
    const res = []
    for (let i=0, len=nums.length; i<len-3; i++) { // target 无限制故无法使用 threeSum 的限制实现剪枝
        if (i>0 && nums[i]===nums[i-1]) continue // 传统去重剪枝
        for (let j=i+1; j<len-2; j++) {
            if (j>i+1 && nums[j]===nums[j-1]) continue
            const arr = twoSum(nums, j+1, target-nums[i]-nums[j])
            arr.forEach(item => res.push([nums[i], nums[j], ...item]))
        }
    }
    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
}

# 方法 2 排序+双指针夹逼(复用twoSum版本 & 加入剪枝)

思路:
- 复用：复用 threeSum 的解题方式，即套用其 twoSum 解题模板
- 剪枝：由于 target 无限制故无法使用 threeSum 的限制实现剪枝，使用新的 min 和 max 剪枝有效减少无效计算.
复杂度：
- 时间 O(n^3). 排序 O(nlogn) + 遍历*左右指针的夹逼 O(n^3).
- 空间 O(n) 计算 twoSum 时借助了与结果数量相同的额外空间，最好情况即无结果为, 最坏情况结果亦小于N, 故 O(n).
结果：
- 执行用时：124 ms, 在所有 JavaScript 提交中击败了43.12%的用户
- 内存消耗：43 MB, 在所有 JavaScript 提交中击败了9.27%的用户

var fourSum = function(nums, target) {
    if (!nums || nums.length<4) return []
    nums.sort((a, b) => a-b)
    const res = []
    for (let i=0, len=nums.length; i<len-3; i++) { // target 无限制故无法使用 threeSum 的限制实现剪枝
        if (i>0 && nums[i]===nums[i-1]) continue // 传统去重剪枝
        if ((nums[i]+nums[i+1]+nums[i+2]+nums[i+3])>target) break // min 剪枝
        if ((nums[i]+nums[len-3]+nums[len-2]+nums[len-1])<target) continue // max 剪枝,退出前会重复N次
        for (let j=i+1; j<len-2; j++) {
            if (j>i+1 && nums[j]===nums[j-1]) continue
            if ((nums[i]+nums[j]+nums[j+1]+nums[j+2])>target) break
            if ((nums[i]+nums[j]+nums[len-2]+nums[len-1])<target) continue
            const arr = twoSum(nums, j+1, target-nums[i]-nums[j])
            arr.forEach(item => res.push([nums[i], nums[j], ...item]))
        }
    }
    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 都将助力我产出更好内容~