梦开始的地方

⼀段优美的前⾔，哟，哟：

● 年轻的码农哟~ 你是不是⼀直在思考⾃我提升的问题~

● 思来想去，决定从算法抓起（单押）~

● 拿起⼜放下，经历过多少次放弃（单押 ✖ 2）~

● 决定了！这次让我来帮你梳理（单押 ✖ 3）！Skr~

坦诚相⻅吧，两数之和！

● 《两数之和》是算法学习过程中最最经典也是最最基础的⼀个问题。

● ⼒扣、⽜客等刷题⽹站排⾏最⾼的就是两数之和了，经典就有其经典的道理，《两数之和》因为本身并没有太⾼的难度，⽽

● 且也能体现出⼀些算法的思想，所以作为⼊⻔必刷题来说，再合适不过了。

那么咱们先来看题目吧

● 确定一个目标值

● 接下来就是需求分析

○ 从给出的 nums 数组中找到两个数字, 两个数字的和是 target

○ 有且只有一个唯一解

○ 找到两个数字以后, 返回两个数字的下标

● 比如

○ 这里的答案就是 2 和 5

○ 因为 nums[2] + nums[5] = 9 符合要求

开始搞起来

暴力破解

作为一个入门的程序员, 一个小趴菜, 我都觉得这个玩意对于我来说实在是太简单了

明⽩了！挨个对⽐挨个找⼀遍不就得了，小小问题，难不倒真正的勇⼠，看我破他护体真⽓，双重循环暴⼒解法奉上！

● 完全没有问题, 搞定, 我真是太棒了

给我的小伙伴们看完这个答案以后, 我的嘴角微微上扬, 已经准备好接受大家的表扬了

你们这是什么眼神, 我怎么了, 难道不对吗 ??

但是提交上去之后，分数并不⾼，说这种⽅法性能不好，暴⼒解法采⽤双重循环嵌套的话，虽然解决了问

题，但是执⾏判断的次数⼤约是：(n-1) + (n-2) + (n-3) + ... + 1次

● 从之前学过的时间复杂度来分析的话，暴⼒解法的时间复杂度⼤约是O(n(n-1))即O(n²-n)，虽然时间复杂度⼩于O(n²)，但是

● 实际也没好到哪⼉去，当然分数不⾼咯。

● 好吧，好吧，真是拿你没有办法（扶眼镜）~，接下来，我们来转换思路，另辟蹊径！

秘法 · 空间换时间

● 所谓的空间换时间，其实指的就是，针对这样两层遍历的情况，我们可以在遍历的过程中，⼀边去判断，⼀边做存储，判断

● 找到了就返回，没找到，那就存起来等到下⼀次判断的时候看看是否能找的到，这样⼀边判断、⼀边存储的⽅式当然快咯，

● 因为毕竟只需要遍历⼀次嘛，呐，举个栗⼦：

● 有⼀队⼩朋友，要找到他们做任务的搭档，我们就可以先挨个把⼩朋友叫过来（开始遍历），让他从⼀个本⼦上去找，看本 ⼦上的照⽚有没有⾃⼰的搭档（做判断）。

● 如果找到了，那⼩朋友就可以⼤声报告出来（返回结果），如果没找到呢，就把这个⼩朋友的照⽚贴在本⼦上，然后叫下⼀ 个⼩朋友进来找（存储后继续遍历）。

● 这样是不是性能和效率就⾼很多了，⾮常Nice，换个思路，果然有另外收获！

● 好了，开打，开打！代码奉上！

● 这次的⽅法，我们只⽤了⼀次循环，就解决了问题，时间复杂度当然就是O(n)咯，只是在函数运⾏的过程中，创造了⼀个 map对象在占⽤内存空间，虽然函数之后map对象被回收了，但是总的来说是消耗了⼀些内存的。

● 但是虽然计算的时候占⽤了内存，但是⾮常明显的提⾼了效率和性能，ok，ok，得偿所愿！

最后划⼀个道道

● 所以说，所谓的空间换时间，真的⾮常适合⽤在⼀些查找类的算法需求中，以后再碰到这样的需求，我们不要再研究双重循

● 环嵌套查找啦，来尝试下空间！换！时间吧！少年！咱们下期再⻅ヾ(￣▽￣)Bye~Bye~