首页 > 算法(附思维导图 + 全部解法)300题16最接近的三数之和
头像
码农三少
发布于 2021-08-29 20:28
+ 关注

算法(附思维导图 + 全部解法)300题16最接近的三数之和

零 标题:算法(leetode,附思维导图 + 全部解法)300题之(16)最接近的三数之和

导读:

作者简介

1 作者简历

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

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 ,若失效的话可私信本人以进行最新资料的获取):

理财书籍pdf
技术书籍pdf
个人基金

全部评论

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

相关热帖

热门推荐