search

yuanyuanbyte / Blog

圆圆的博客，预计写七个系列：JavaScript深入系列、JavaScript专题系列、网络系列、Webpack系列、Vue系列、JavaScript基础系列、HTML&CSS应知应会系列。
306 stars 125 forks source link

算法入门系列之 2sum #95

Open yuanyuanbyte opened 2 years ago

yuanyuanbyte commented 2 years ago

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

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

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

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 '无二和解'
};

性能如下：

在这里插入图片描述

两种解法的对比

直接上图：

在这里插入图片描述

查看原文

博文系列目录

交流

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

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

weixin