两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

1、 保持数组中的每个元素与其相互对应的最好方法是什么？哈希表

通过空间换取速度，将查找时间O（n）降低到O（1），哈希表构建就是为了达到这个目的。它以近似恒定的时间来进行快速查找。

这里我们将进行两次遍历，第一次将每个元素的值和key分别作为hash表的key和值，添加到表中。第二次遍历，检查每个元素对应的目标元素(target - nums[i])是否存在hash表中，如果存在，且两个元素不是本身，则就得出两个元素的索引，得出对应解。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashMap = {}
        for i, num in enumerate(nums):
            hashMap[num] = i
        for i,num in enumerate(nums):
            component = target - num
            j = hashMap.get(component)
            if j is not None and i != j:
                return [i,j]

2、优化下代码，换个更加有意思的思路，做一次遍历。

目标数存在hashmap中，则得到相应解，如果不存在hash表中，则将遍历的元素作为key插入hash表中，对应的索引作为value插入hash表中

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashMap = {}
        for i,num in enumerate(nums):
            component = target - num
            j = hashMap.get(component)
            if j is not None and i != j:
                return [i,j]
            else:
                hashMap[num] = i