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

导读：

作者简介

1 作者简历

2 作者标签

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

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

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

一 题目描述

二 解法总览（思维导图）

三 全部解法

1 方案1

1)代码：

// 方案1 “暴力 - 3层for循环”。
// 技巧：虽然穷举是笨方法，但在数据量不是很大的情况下是可以work的。
var threeSumClosest = function(nums, target) {
    const l = nums.length;

    // 1）状态初始化
    // minDiffValue：当前3个数之和 与 target 的差的绝对值。
    let minDiffValue = Number.POSITIVE_INFINITY,
        resSum;

    // 2）核心：3层for循环，穷举所有的可能。
    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++) {
                // 2.1）根据 nums[i] + nums[j] + nums[k] 和 target 计算出 tempDiffValue ，
                // 若 tempDiffValue < minDiffValue
                // 更新 resSum 和 minDiffValue 。
                const tempSum = nums[i] + nums[j] + nums[k];
                const tempDiffValue = Math.abs(tempSum - target);
                if (tempDiffValue < minDiffValue) {
                    resSum = tempSum;
                    minDiffValue = tempDiffValue;
                }
            }
        }
    }

    // 3）返回结果 resSum 。
    return resSum;
};

2 方案2

1)代码：

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

    // 1）状态初始化
    // minDiffValue：当前3个数之和 与 target 的差的绝对值。
    let minDiffValue = Number.POSITIVE_INFINITY,
        resSum;

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

    // 3）核心：遍历 + 双指针
    for (let i = 0; i < l - 2; i++) {
        let left = i + 1,
            right = l - 1;

        while (left < right) {
            const tempSum = nums[i] + nums[left] + nums[right];
            const tempDiffValue = Math.abs(tempSum - target);

            // 3.1）若 tempDiffValue < minDiffValue,
            // 则 更新 resSum 和 minDiffValue 值。
            if (tempDiffValue < minDiffValue) {
                resSum = tempSum;
                minDiffValue = tempDiffValue;
            }

            // 3.2）根据 当前3个数之和 与 target 的比较，
            // 决定让tempSum 变小（right--） 还是 变大（left--）。【注：因为nums已升序排序】
            if (tempSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

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

3 方案3

1)代码：

var threeSumClosest = function(nums, target) {
    const l = nums.length;

    // 1）状态初始化
    // minDiffValue：当前3个数之和 与 target 的差的绝对值。
    let minDiffValue = Number.POSITIVE_INFINITY,
        // 优化：多了map。作用：快速判断 “当前3数组合”是否存储过。
        map = new Map(),
        resSum;

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

    // 3）核心：遍历 + 双指针，结合 map 快速判断 “当前3数组合”是否存储过。
    for (let i = 0; i < l - 2; i++) {
        let left = i + 1,
            right = l - 1;

        // 优化：若“当前3数组合”已经存储过了，
        // 则 直接continue、进入下一次循环。
        // 若没有，则 map.set(tempStr, 1); 。
        const tempStr = [nums[i], nums[left], nums[right]].join('#');
        if (map.has(tempStr)) {
            continue;
        } else {
            map.set(tempStr, 1);
        }

        while (left < right) {
            const tempSum = nums[i] + nums[left] + nums[right];
            const tempDiffValue = Math.abs(tempSum - target);

            // 3.1）若 tempDiffValue < minDiffValue,
            // 则 更新 resSum 和 minDiffValue 值。
            if (tempDiffValue < minDiffValue) {
                resSum = tempSum;
                minDiffValue = tempDiffValue;
            }

            // 3.2）根据 当前3个数之和 与 target 的比较，
            // 决定让tempSum 变小（right--） 还是 变大（left--）。【注：因为nums已升序排序】
            if (tempSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

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

四 内推&更多

1 内推

本人是百度的1名工程师，欢迎校招、社招同学向本人投递简历。
本人可内推公司（也可帮忙内推 阿里、腾讯、字节、美团、滴滴、京东等）的所有岗位，欢迎私信。

2 更多

以下是个人整理的一些笔记和书籍（永久有效链接: https://pan.baidu.com/s/1SPc3umO6cZlBtoPylSaHzw 密码: eqee ，若失效的话可私信本人以进行最新资料的获取）：