Leetcode

twosum

​ 两数之和作为Leetcode序列号为1的题目，对新手具有十足的劝退性。
​ 如果暴力求解，用两重循环不断遍历，这可能是自然而然的思路，但写起来也并不好写。
​ 本题的官方标签是”哈希表”， 所以本篇题解只讨论用哈希表来求解此题。
​ 对于很多同学来说，会不会哈希先放在一边，为什么会想到用哈希表才是头疼的地方。
​ 那么我们可以先不先入为主地考虑哈希，来分析一下这道题：
​ 首先，写第一个for循环来遍历这个数组来查看每一个值是自然而然的想法。
​ 

1
2
3
for (int i = 0; i < nums.size(); ++i) {
		……
}

​ 就示例1而言，当i为0的时候，我们遍历到nums[0] ：2，它是否是答案呢？不知道。我们需要继续向后遍历。
​ 当i为1的时候，我们遍历到nums[1]：7，它是否是答案呢？
​ 当然，它加上前面的2就是我们的target：9，但问题来了：作为人类，你当然可以向前看一个，但是作为程序，它并没有”回头看”的能力。既然如此，我们就必须为程序创造一个用来记忆的东西。
​ 这种记忆能力需要什么呢？
​ 第一：需要能同时存储下标i及对应数值nums[i]的能力，因为我们既需要查看之前遍历过的数值，还需要知道它的下标（答案需要我们返回下标）；这就要求我们选取的数据结构具有存储二元组的能力。
​ 第二：具有查看效率高的能力，因为每当我们遍历数组中的一个值，都会对之前遍历过的数据进行搜索。
​ 综上，哈希表脱颖而出。
​ 如果你对哈希表不太清楚，欢迎你在评论区留言，但在题解中就不过多赘述了。
​ 接下来我们创建一个哈希表，来补充刚刚的程序。

1
2
3
4
unorderd_map<int, int> heap;
for (int i = 0; i < nums.size(); ++i) {
		……
}

​ 接下来，我们需要把思路转个弯，有了哈希表之后，我们已经可以非常快速的在哈希表里找到想要找到的值，那么我们要在里面找谁呢？
​ 现在我们有nums[i]， target，而如果nums[i]是答案之一，另一个答案是什么呢？当然是target - nums[i]。
​ 所以我们不用再往后看是否有答案了，我们可以在前面找，因为前面的值和下标已经被我们添加到哈希表里。
​ 如果我们在哈希表里找到这个答案：target - nums[i]， 那么我们就找到了整个题目的答案，直接返回即可。

1
2
3
4
5
6
7
unorderd_map<int, int> heap;
for (int i = 0; i < nums.size(); ++i) {
		int tmp = target - nums[i];
		if (heap.find(tmp)) return {heap[tmp], i};
		heap[nums[i]] = i;
}
return {};