18. 4Sum

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */

这题就是 3 sum 的再进阶版

本题给了一个数字数组 nums 以及一个 target

要求我们在 nums 中找到任意四个元素，使得其和为 target

要求返回所有不重复的四元组

解题思路

3 sum = 一个循环+双指针

4 sum = 两个循环+双指针

记得去除重复的元组就好

Javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    const len = nums.length
    const res = []
    if (len < 4) {
        return res
    }
    nums.sort((a, b) => a - b)

    for (let i = 0; i < len - 3; i++) {
        // skip duplicate
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        for (let j = i + 1; j < len - 2; j++) {
            // skip duplicate
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue
            }

            let left = j + 1
            let right = len - 1
            const sum = nums[i] + nums[j]

            while (left < right) {
                const total = sum + nums[left] + nums[right]

                if (total < target) {
                    left++
                } else if (total > target) {
                    right--
                } else {
                    res.push([nums[i], nums[j], nums[left], nums[right]])
                    left++
                    right--

                    // skip duplicate
                    while (nums[left] === nums[left - 1] && left < right) {
                        left++
                    }
                    while (nums[right] === nums[right + 1] && right > left) {
                        right--
                    }
                }
            }
        }
    }

    return res
};