18. 四数之和

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

时空复杂度

时间复杂度：O(n^3)

空间复杂度: O(1)

改一下 threesum 就是套娃

var threeSum = function (nums, start, highTarget) {
    let res = []
    if (nums.length < 3) return []
    for (let i = start; i < nums.length; i++) {
        let left = i + 1
        let right = nums.length - 1
        let target = highTarget - nums[i]
        while (left < right) {
            const leftCarry = nums[left]
            const rightCarry = nums[right]
            const sum = leftCarry + rightCarry
            if (sum === target) res.push([nums[i], leftCarry, rightCarry])

            if (sum <= target) while (left < right && nums[left] == leftCarry) left++
            if (sum >= target) while (left < right && nums[right] == rightCarry) right--
        }
        while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++
    }
    return res
};
var fourSum = function (nums, target) {
    let res = []
    if (nums.length < 4) return []
    nums.sort((a, b) => a - b)
    for (let i = 0; i < nums.length; i++) {
        let data = threeSum(nums, i + 1, target - nums[i])
        data.forEach(v => res.push([nums[i], ...v]))
        while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++
    }
    return res
};

扩展 nSum

将 for 循环中 找值的操作作为 n=2 时的递归终止操作，将找到的数组往上递归拼接

var fourSum = function (nums, target) {
    let res = []
    nums.sort((a, b) => a - b)
    return nSum(nums, target, 0, 4)
};
var nSum = function (nums, target, start, n) {
    if (n < 2 || nums.length < n) return []
    let res = []
    if (n == 2) {
        let left = start
        let right = nums.length - 1
        while (left < right) {
            const leftCarry = nums[left]
            const rightCarry = nums[right]
            const sum = leftCarry + rightCarry
            if (sum === target) res.push([leftCarry, rightCarry])
            if (sum <= target) while (left < right && nums[left] == leftCarry) left++
            if (sum >= target) while (left < right && nums[right] == rightCarry) right--
        }
    } else {
        for (let i = start; i < nums.length; i++) {
            let data = nSum(nums, target - nums[i], i + 1, n - 1)
            data.forEach(v => res.push([nums[i], ...v]))
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++
        }
    }
    return res
}

参考回答