“我有n个数字的列表，里面有且仅有两个数之和等于m，我要知道这两个数字在哪。”
这就是LeetCode中”Hello World”级别的问题所要解决的事情。
用最简单的思路，我们可以这么做：
- 拿起第 1 个数字，看它后面的数字和它相加是否等于 , 如果存在这个数字，问题解决；
- 拿起第 2 个数字，看它后面的数字和它相加是否等于 , 如果存在这个数字，问题解决；（注意，我们都只看后面的数字，因为前面的数字我们已经检查过了）
- … 拿起第 个数字，看它后面的数字和它相加是否等于 , 如果存在这个数字，问题解决；
我们需要遍历一遍这个列表，找到每个元素后面是否存在一个数字和它相加等于 .
这样做听起来很合理，但是复杂度其实是 . 因为对于遍历的第 个元素，我们要检查第 共 个元素中是否有和第 个元素相加等于 的数字。 所以最坏情下，算法复杂度估计如下：
我们能让算法更快吗？
其实是可以的。我们只用一个哈希表，在遍历数组时，实时将数字与其索引存入。对于每个数字，我们计算其配对值（即目标值减去当前值），然后检查这个配对值是否已经在哈希表中。如果在，就说明找到了两个数，直接返回它们的索引；如果不在，就将当前数字及其索引存入哈希表，继续向后遍历。这样，只需一次遍历，时间复杂度和空间复杂度都是 O(n)。
—— “用空间换时间”