一、题目

如果你刷过LeetCode，你一定知道第一题，“两数之和”。因为我们刷题一般都是从第一题开始的，他也是被LeetCode网站定义为难度为简单的一道题，让我们先来看看他的题目描述：

给定一个整数数组 nums 和一个整数目标值 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 <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

二、暴力枚举法

我们首先会想到的方法自然是暴力枚举法，毕竟这是一个既好理解又好写的方法，甚至它还很节省内存。

对于数组里的每一个元素x，在数组中寻找target-x。

时间复杂度O(N²)，空间复杂度O(1)。

空间复杂度很优秀。可惜，空间就像我的感情一样，是最不值钱的东西。而它浪费了最宝贵的资源——时间。

三、在此思路上改进一下？

在这个基础上，改进一下？

“emm……在数组中查找……”

有了，使用二分查找法更快！

首先使用快排，对数组排序，对于数组里每一个元素x，在数组中二分查找target-x。（禁止中二）

时间复杂度O(nlogn)，已经大大进化了，至于空间复杂度，Who cares！

其实，这个方法还可以继续优化。但是既然使用到了排序，时间复杂度就无法突破O(nlogn)，继续优化只不过是细枝末节，并没有质的突破。

四、哈希Map，真香

其实我们不难注意到题目中这样两句理想化的描述：

• 你可以，假设每种输入只会对应一个答案。
• 只会存在一个有效答案

如果你使用java语言并且了解过HashMap（其他语言也有类似实现，比如C++叫做std::hash_map、python叫做字典），你一定会感叹：“这题目简直就是为了HashMap出的！”

这里引用LeetCode网站给出的Java语言的参考答案。

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
 4         for (int i = 0; i < nums.length; ++i) {
 5             if (hashtable.containsKey(target - nums[i])) {
 6                 return new int[]{hashtable.get(target - nums[i]), i};
 7             }
 8             hashtable.put(nums[i], i);
 9         }
10         return new int[0];
11     }
12 }

创建HashMap，使用数组中的元素作为key，对应的索引作为value。对于数组里的每一个元素x，首先寻找HashMap中是否存在key为target-x的节点，如果有则返回，如果没有则把x加入到HashMap中。

由于HashMap的出色设计，使这种解题方法的时间复杂度达到了令人惊艳的O(N)。妙啊，真是太妙了。

五、还可以继续优化追求极限性能吗

使用HashMap解决这道问题表现出的性能优势已经足够令人惊艳。那，真的还可以继续优化吗？这就需要我们了解HashMap的底层原理了，欲知详情请看下集……（还可以再水一篇）

 原文：https://www.cnblogs.com/ohayo/p/14503264.html