算法（附思维导图 + 全部解法）300题之（15）三数之和

零标题：算法（leetode，附思维导图 + 全部解法）300题之（15）三数之和

导读：

作者简介

1 作者简历

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

2 作者标签

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

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

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

一题目描述

题目描述

二解法总览（思维导图）

思维导图

三全部解法

1 方案1

1)代码：

// 方案1 “暴力”。3层for循环，超时、通过 315 / 318 。
// 技巧：涉及“数量、重复、唯一性”可优先考虑 hash （JS里的 map数据结构 ）
var threeSum = function(nums) {
    const l = nums.length;
    // map：判断是否重复 —— 即之前是否存过该答案
    // 1）初始化 map 和 resArr
    let map = new Map(),
        resArr = [];

    // 2）3层for循环。i范围[0, l - 3]，j范围[i + 1, l - 2]，k范围[j + 1, l - 3]。
    for (let i = 0; i < l - 2; i++) {
        for (let j = i + 1; j < l - 1; j++) {
            for (let k = j + 1; k < l; k++) {
                // 3）核心处理
                const tempSum = nums[i] + nums[j] + nums[k];
                if (tempSum === 0) {
                    // 3.1）当 nums[i] + nums[j] + nums[k] === 0 时，
                    // 判断此时3个数所组成的答案之前有没有存过，没有就保存到 resArr 里
                    const tempStr = [nums[i], nums[j], nums[k]].sort().join('#');
                    if (!map.has(tempStr)) {
                        // 注：此处的 1 无意义，仅表示 tempStr 的答案存储过了
                        map.set(tempStr, 1);
                        resArr.push([nums[i], nums[j], nums[k]]);
                    }
                }
            }
        }
    }

    return resArr;
};

2 方案2

1)代码：

// 方案2 “排序 + 双指针”。
// 技巧：佛说：“有序胜过无序”。
// 通过sort方法（时间复杂度仅为 O(nlogn)）将无序的数组变有序是一件很划算的事情。
var threeSum = function(nums) {
    // 1）排序（升序）
    nums = nums.sort((a, b) => a-b);

    const l = nums.length;
    let resArr = [];

    for(let i = 0; i< l-2; i++) {
        // 边界：因为升序排的，若 nums[i] > 0，
        // 则必有 nums[i] + nums[left] + nums[right] > 0，需终止循环遍历
        if (nums[i] > 0) {
            break;
        }
        // 边界：[0, 0, 0, 0]等。本质："去第1个数的重"。此时需直接进入下一个循环
        if (nums[i - 1] === nums[i]) {
            continue;
        }

        let left = i + 1;
        let right = l - 1;

        // 2）核心：固定1个数之后，
        // 就变成了“双指针”（本质就是twoSum，2个数之和为 (-1) * nums[i]）问题。
        while (left < right) {
            // 边界：[-1, 0, 0, 1, 1]。本质："去第2个数的重"。
            if (left - 1 !== i && nums[left] === nums[left - 1]) {
                left++;
                continue;
            }
            const tempSum = nums[i] + nums[left] + nums[right];
            if (tempSum === 0) {
                // 3）找到之后，肯定不会重、直接放入 resArr。
                // 处理：left、right同时往中间靠。
                resArr.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
            } else if (tempSum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

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

3 方案3

1)代码：

// 方案3 回溯（说白了、说穿了，就是递归。因为一般用递归实现回溯）。
// 本质：其实跟3层for循环差不多，超时。通过 315 / 318。
var threeSum = function(nums) {
    // 深度优先遍历。
    // 技巧：递归 = 递归出口 + 递归主体。
    const dfs = (index, l, curArr, resArr) => {
        const curLength = curArr.length;

        // 1）递归出口。index过大 || “当前记录数组”长度 > 3
        if (index > l ||  curLength> 3) {
            return;
        }

        // 2）递归主体。
        // 2.1）当 “当前记录数组”长度 === 3，需要判断是否为3个数之和为0且未重复存储过。
        if (curLength === 3) {
            const tempSum = curArr.reduce((acc, cur) => {
                return acc += cur;
            }, 0);
            const tempStr = curArr.join('#');

            if (tempSum === 0 && !map.has(tempStr)) {
                // 边界：必须是 curArr.slice() 、存其副本！
                // 若直接写的 curArr 就是存的引用，会因引用引起问题
                resArr.push(curArr.slice());
                map.set(tempStr, 1);
            }
        }
        // 2.2）当 “当前记录数组”长度 < 3，需要进行回溯遍历（即 选 与 不选 ）。
        else if (curLength < 3) {
            const newIndex = index + 1;
            // 核心：所谓的“回溯”本质 —— 选 与 不选。
            // 2.2.1）选
            curArr.push(nums[index]);
            dfs(newIndex, l, curArr, resArr);
            // 2.2.2）不选
            curArr.pop();
            dfs(newIndex, l, curArr, resArr);
        }
    };


    const l = nums.length;
    // 1）排序。去重有用， const tempStr = curArr.join('#'); 。
    nums = nums.sort((a, b) => a - b);

    // 2）“状态”初始化
    let index = 0,
        // 作用：记录是否重复
        map = new Map(),
        curArr = [],
        resArr = [];

    // 3）调用回溯函数 —— dfs
    dfs(index, l, curArr, resArr);

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