面试题01.02. 两数之和

野性酷女 2023-01-17 14:50 128阅读 0赞

面试题01.02. 两数之和

> 前言：主要目的是为了持续输出，用浅显易懂，各种各样的方式来解析算法题，同时提高算法能力。答主的水平也有限，大家共同进步。

## 面试题01.02. 两数之和 ##

题目：

#### 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 ####

##### 示例1： #####

输入：nums = [2,7,11,15], target = 9
    输出：[0,1]

##### 示例2： #####

输入：nums = [3,2,4], target = 6
    输出：[1,2]

最简单的办法，暴力双循环

##### 1. 双循环相加判断 #####

执行用时：84 ms, 在所有 JavaScript 提交中击败了65%的用户  
内存消耗：37.9 MB, 在所有 JavaScript 提交中击败了69%的用户

解析：我们先分析题目，希望数组中不重复的两项相加和为某数，最先想到的办法就是将每一项都相加，直到得到正确答案为止。所以，我们先写一个循环循环数组中的每一项，之后得到`first`,`first`就是我们的其中一项了，那如何找到另一项呢？在获取到`first`的值后，再进行一次循环，让`first`与除了自身之外的每一项相加，结果与`target`进行对比，直至找出最终结果。

##### 2. 优化方案一 #####

执行用时：84 ms, 在所有 JavaScript 提交中击败了66%的用户  
内存消耗：37.7 MB, 在所有 JavaScript 提交中击败了96%的用户

解析：此方案是我在写1的解析时想到的方案，作为对1暴力破解的优化版本,可以看到我在代码中写的注释，其实解法一中有很多重复计算的步骤。我们第二次循环的时候从第一个参数后一位开始，就可以去除重复的循环了，但运行时间和内存，和第一种方法并没有差很多。。。我表示不服。。。（PS：果然，分享人才是最大的受益者，也希望大家可以多多分享。）

##### 3. 缓存查找另一半 #####

执行用时：84 ms, 在所有 JavaScript 提交中击败了65%的用户  
内存消耗：37.9 MB, 在所有 JavaScript 提交中击败了60.71%的用户

解析：此方案仍可作为解法一与解法二的优化版，最突出的亮点在于只用了一个循环，但主要是利用了其他数据结构，本质仍然是两个循环在查找而已。利用对象将数组的每一项存储起来，值为下标，key为每一项的值，这样设置的目的主要在于可以直接通过对象\[属性名\]的方式找到值，此解法需要注意的点是在js中会将0认为是假，如果正确结果中含有0的下标就要挂掉了。。。所以在if判断的时候改成了与`undefined`进行对比。

#### 总结 ####

其实这三种方案的思路和本质都类似，主要区别就是优化、优化、继续优化。我们平时在写代码的时候其实也需要这样的思路，并不是要将需求完成就好了，而是面对自己写的每一行代码问一句，这行代码能删掉吗？希望我们程序中运行的每一行代码都能够发挥自己的作用。

贴上一张图吧，其实这道题我已经做了很多遍了，常做常新。