1 · 两数之和

给定一个整数数组 nums 和一个整数 target。 请你在数组中找出两个整数，使它们的和等于 target，并返回这两个整数的下标。

输入

nums = [2, 7, 11, 15]
target = 9

输出

[0, 1]

解释

因为：

nums[0] = 2
nums[1] = 7

2 + 7 = 9

所以返回：

[0, 1]

函数 两数之和(nums, target):

    已出现 = 空字典

    对于 下标, 当前数字 遍历 nums:

        需要的数字 = target - 当前数字

        如果 需要的数字 在 已出现 中:

            返回 [
                需要的数字对应的下标,
                当前下标
            ]

        记录 当前数字对应的下标

核心思想：

不是：

当前数字 + 另一个数字 = target

而是把它变成：

另一个数字 = target - 当前数字

比如：

当前数字 = 7
target = 9

需要的数字 = 9 - 7
          = 2

于是问题就变成：

前面有没有出现过 2？

如果出现过：

答案找到了

class Solution:
    def twoSum(self, nums, target):

        # 记录之前已经见过的数字。
        # key 是数字，value 是这个数字的下标。
        seen = {}

        # i 是当前数字的下标。
        # num 是当前正在处理的数字。
        for i, num in enumerate(nums):

            # 算出当前数字还需要搭配哪个数字。
            # 例如 target=9，num=7，那么 need=2。
            need = target - num

            # 如果需要的数字之前已经出现过，
            # 就说明 need + num 正好等于 target。
            if need in seen:

                # seen[need] 是之前那个数字的下标。
                # i 是当前数字的下标。
                return [seen[need], i]

            # 当前还没找到答案。
            # 把当前数字和它的下标记录下来。
            seen[num] = i

原数据：

nums = [2, 7, 11, 15]
target = 9

初始状态：

seen = {}

第 1 次循环

i = 0
num = 2

计算：

need = target - num

代入：

need = 9 - 2
     = 7

现在问：

seen 里面有 7 吗？

目前：

seen = {}

没有。 所以记录：

seen[2] = 0

现在：

seen = {
    2: 0
}

意思是：

数字 2
出现在下标 0

第 2 次循环

i = 1
num = 7

计算：

need = target - num

代入：

need = 9 - 7
     = 2

现在问：

seen 里面有 2 吗？

有：

seen = {
    2: 0
}

所以：

2 + 7 = 9

答案找到了。 执行：

return [seen[2], 1]

因为：

seen[2] = 0

所以：

return [0, 1]

最终过程

最终：

[0, 1]

这题你真正要记住的一句是：

need = target - num

然后：

看看 need 之前出现过没有

这就是这题哈希表解法的核心。

时间复杂度：O(n) 空间复杂度：O(n)