算法入门系列之 2sum

[yuanyuanbyte]

本系列的主题是算法入门，每期重点攻克一个技术重难点，如果你还不了解各系列内容，文末点击查看全部文章。

如果觉得本系列不错，欢迎点赞、评论、转发，您的支持就是我坚持的最大动力。

图片加载失败的话，文章末尾点击查看原文，即可正常观看，点我跳转到文末

2sum

题目描述

1.暴力法

暴力法很简单，即双重遍历

第一次提交

实际上，这是第二次提交，可以看到第一次解答错误，因为我没有认真看题，以为是返回那两个目标值，导致结果出来之后我甚至有点诧异，粗心啊粗心，重新看了一遍题，改成下标就好了。

代码如下：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    for (let index = 0; index < nums.length; index++) {
        for (let index2 = 0; index2 < nums.length; index2++) {
            let num2 = nums[index2];
            if (index != index2) {
                let sum = num1 + num2;
                if (sum == target)
                    return [index, index2]
            }
        }
    }
};

性能如下：

第二次提交

看官方题解后，优化代码
事实上，我刚开始看官方题解有点疑惑，觉得这个题解不会是错的吧，然后我就演算了一下，发现这tm是最优解啊。。。
演算如下：

第二次提交：

性能如下：

两种算法的性能对比

对比可以看出，两者在空间复杂度上相差无几，但在时间复杂度上，后者（最优解）是前者的两倍。

后者（最优解）完胜

2.拿空间换时间

第三次提交

想到了大佬说的拿空间换时间，但是自己没有思路，看了大佬的代码，ok，看懂了，wt？这是什么意思？
好吧~再来演算一遍

演算如下：

演算一遍后思路清晰了很多~

第三次提交：

代码如下：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let obj = {};
    for (let index = 0; index < nums.length; index++) {
        num = nums[index];
        if (num in obj) {
            return [obj[num], index]
        } else {
            obj[target - num] = index
        }
    }
    throw '无二和解'
};

性能如下：

两种解法的对比

直接上图：

查看原文

博文系列目录

• JavaScript 手写系列
• JavaScript 深入系列
• JavaScript 基础系列
• 网络系列
• 浏览器系列
• 性能优化与网络安全系列
• Webpack 系列
• Vue 系列
• HTML 应知应会系列
• CSS 应知应会系列
• 算法入门系列

交流

各系列文章汇总：https://github.com/yuanyuanbyte/Blog，内有优质前端资料，觉得不错点个star。

我是圆圆，专注于打造一系列能够帮助前端工程师提高的优质文章，希望我的文章能对你的学习成长有所帮助，一起加油！