首页 > 算法(附思维导图 + 全部解法)300题之(18)四数之和
头像
码农三少
发布于 2021-09-03 09:49
+ 关注

算法(附思维导图 + 全部解法)300题之(18)四数之和

零 标题:算法(leetode,附思维导图 + 全部解法)300题之(18)四数之和

导读:

作者简介

1 作者简历

作者简历
2019年的微信小程序应用开发赛-全国三等奖

2 作者标签

1)“伪全栈工程师,主攻前端,偶尔写点后端”。

2)2019年的微信小程序应用开发赛 - 全国三等奖;
2019CODA比赛 - 前 17/211 强 且 荣获“优秀团队”称号 等。

3)“半自媒体人”,在校期间、个人公众号(IT三少。新自媒体(公众号)号: 码农三少 )在半年内实现了0到5.8K+的粉丝增长等。

一 题目描述

题目描述

二 解法总览(思维导图)

思维导图

三 全部解法

1 方案1

1)代码:

// 方案1 “暴力”。
// 先排序,再4层for循环、穷举所有的可能。
// 超时,通过 282 / 286 。
var fourSum = function(nums, target) {
    const l = nums.length;

    // 1)排序。
    nums = nums.sort((a, b) => a - b);

    // 2)状态初始化。
    let map = new Map(),
        resArr = [];

    // 3)核心:4层for循环、穷举所有的可能。
    for (let i = 0; i < l-3; i++) {
        for (let j = i + 1; j < l-2; j++) {
            for (let k = j + 1; k < l-1; k++) {
                for (let z = k + 1; z < l; z++) {
                    const tempSum = nums[i] + nums[j] + nums[k] + nums[z],
                        tempStr = [nums[i], nums[j], nums[k], nums[z]].join('#');

                    // 3.1)判断“当前4个数组合的和” 是否等于 target 且 之前没有存储过。
                    if (tempSum === target && !map.has(tempStr)) {
                        resArr.push([nums[i], nums[j], nums[k], nums[z]]);
                        map.set(tempStr, 1);
                    }
                }
            }
        }
    }

    // 4)返回结果 resArr 。
    return resArr;
};

2 方案2

1)代码:

// 方案2 “方案1的优化版”。
// 原先的4层for循环 --> 2层for循环 + 双指针 。
// 技巧:“有序胜过无序”。
// 通过sort方法(时间复杂度仅为 O(nlogn))将无序的数组变有序是一件很划算的事情。
// 要想使用双指针等,必须先排序、使其变有序。
var fourSum = function(nums, target) {
    const l = nums.length;

    // 1)排序。
    nums = nums.sort((a, b) => a - b);

    // 2)状态初始化。
    let map = new Map(),
        resArr = [];

    // 3)核心:2层for循环 + 双指针 。
    for (let i = 0; i < l-3; i++) {
        for (let j = i + 1; j < l-2; j++) {
            let left = j + 1,
                right = l-1;

            while (left < right) {
                const tempSum = nums[i] + nums[j] + nums[left] + nums[right],
                    tempStr = [nums[i], nums[j], nums[left], nums[right]].join('#');

                // 3.1)判断“当前4个数组合的和” 是否等于 target 且 之前没有存储过。
                if (tempSum === target) {
                    if (!map.has(tempStr)) {
                        resArr.push([nums[i], nums[j], nums[left], nums[right]]);
                        map.set(tempStr, 1);
                    }

                    // 3.2)核心:若 tempSum === target ,
                    // 则下一次的可能结果必须得让 left、right 各往中间至少走一步,不然组合必重复!
                    left++;
                    right--;
                } else if (tempSum < target){
                    left++;
                } else {
                    right--;
                }
            }
        }
    }

    // 4)返回结果 resArr 。
    return resArr;
};

3 方案3

1)代码:

// 方案3 回溯(说白了、说穿了,就是递归。因为一般用递归实现回溯)。
// 本质:跟4层for循环差不多,可能的区别会体现在代码的可读性上。
// 超时,通过 268 / 286 。
var fourSum = function(nums, target) {
    // 技巧:永远记住,递归 = 递归出口(为了不陷入无线递归的死循环) + 递归主体(一般会变更一些参数后,在调用函数本身)。
    // 一般 递归出口 放前面, 递归主体 放后面。
    // 1)递归
    const dfs = (index, l, curArr, resArr, nums, target) => {
        const curLength = curArr.length;
        // 1.1)递归出口。
        // 边界:是 index > l ,而不是 index >= l(这样会遗漏答案,case:[1,0,-1,0,-2,2] 0 )。
        if (index > l || curLength > 4) {
            return;
        }

        // 1.2)递归主体
        if (curLength === 4) {
            const tempSum = curArr.reduce((acc, cur) => {
                acc += cur;
                return acc;
            }, 0),
                tempStr = curArr.join('#');

            // 判断“当前4个数组合的和” 是否等于 target 且 之前没有存储过。
            if (tempSum === target) {
                if (!map.has(tempStr)) {
                    resArr.push(curArr.slice());
                    map.set(tempStr, 1);
                }
            }
        } else if (curLength < 4) {
            // 技巧:回溯的核心 = 选 + 不选 。
            // 1.2.1)选
            curArr.push(nums[index]);
            dfs(index + 1, l, curArr, resArr, nums, target);
            // 1.2.1)不选
            curArr.pop();
            dfs(index + 1, l, curArr, resArr, nums, target);
        }
    };

    // 2)排序。
    nums = nums.sort((a, b) => a - b);

    // 3)状态初始化。
    const l = nums.length;
    let index = 0,
        map = new Map(),
        curArr = [],
        resArr = [];

    // 4)调用 回溯函数 —— dfs递归。
    dfs(index, l, curArr, resArr, nums, target);

    // 5)返回结果 resArr 。
    return resArr;
}

4 方案4

1)代码:

// 方案4 “方案3(回溯)的优化版” —— 剪枝。
// TODO:暂时想不出,跳过。
// case:[-477,-476,-471,-462,-440,-400,-398,-394,-394,-393,-389,-386,-350,-346,-338,-315,-273,-249,-182,-172,-166,-161,-149,-116,-112,-109,-100,-73,-33,-26,-22,-11,6,8,13,19,56,78,101,102,111,140,155,158,181,205,211,225,232,242,254,265,281,308,310,320,320,364,366,381,385,387,443,496,496]
// 1236
var fourSum = function(nums, target) {
    // TODO:暂时想不出,跳过。
}

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

热门推荐