LeetCode精讲——1. 两数之和（难度：简单）

一、题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

二、示例

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

示例 2：

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

示例 3：

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

提示：

2 <= nums.length <= 10^4 -10^9 <= nums[i] <= 10^9 -10^9 <= target <= 10^9

只会存在一个有效答案

进阶：

你可以想出一个时间复杂度小于 O(n2) 的算法吗？

三、解题思路

3.1> “正向”解题思路

步骤一：如果想要快速确定某个元素是否在nums数组中，并且可以快速的获得所在下标index，我们第一反应应该就是将数组维护成一个Map结构，其中key存储数组里的值，value存储的是数组的下标index，但是由于要考虑nums数组终会有相同值的元素，所以value要保存的是数组或者容器结构，如下图所示：

步骤二：获得了Map结构后，我们就可以开始执行查找操作了。由于题目中已经标明就是两个整数相加等于target值，那我们只需要通过target-nums[i]确定待查找的值，然后去Map中查找即可，如下所示：

步骤三：在这个例子中，就从Map中匹配到了key=7，value=[1,3]的这种情况。那么由于i=1，所以我们匹配的另一个整数值就是3了，所以返回的匹配结果就是result=[1, 3]

【总结】 首先，“正向”解题思路跟我们大多数人思考的解题方式是相同的，但是里面存在挺多“麻烦事儿”的，比如Map中的每一个元素的Value都要是数组或者容器类型，这样整体的内存占用空间也会比较大；其次，以上面例子key=7，value=[1,3] ，在这种情况下是可以匹配上的。但是，如果Map存储的是key=7，value=[1]，那么当做匹配逻辑的时候，还要验证指针i和value中存储的下标是否相同，如果相同，则不是匹配的。

最后，以上面的方式代码实现后，无论是执行时间、内存消耗、代码行数都不好。大家可以参考下面内容：4.1> “正向”解题思路——代码实现

3.2> “逆向”解题思路

为什么叫“逆向”呢？这个词的出发点是Map的用途。

在“正向”解题思路中，Map在初始化过程中是先把所有数据都存储，然后作为判断“元素是否存在”的依据。

而在“逆向”解题思路中，Map在初始化过程中什么元素都不放，而当待匹配的元素不存在Map中的时候，才把它放入的Map中。具体步骤如下所示：

步骤一：初始化一个空的Map，i指向的值为2，待匹配的值为12，而12并没有在Map中，所以将2放入到Map中。如下所示：

步骤二：i指向的值为7，待匹配的值为7，而7并没有在Map中，所以将7放入到Map中。如下所示：

步骤三：i指向的值为11，待匹配的值为3，而3并没有在Map中，所以将11放入到Map中。如下所示：

步骤四：i指向的值为7，待匹配的值为7，而7存在于Map中，所以匹配成功，返回结果：**result=[3, 1]**。如下所示：

【总结】 这种“逆向”解题思路只需要一次循环就可以了，并且Map数组不用提前初始化，在性能和内存占用率都很低。具体代码实现可以参考下面内容：4.2> “逆向”解题思路——代码实现

四、代码实现

4.1> “正向”解题思路——代码实现

这种方式无论是执行时间、内存消耗、代码行数都不好，所以我们依然需要去寻求更优雅的解题方式，如下所示：

4.2> “逆向”解题思路——代码实现

我们采取了逆向思维的方式，发现可以巧妙的解决这道问题，如下所示：

今天的文章内容就这些了，最后一句话：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞&分享。

题目来源：力扣