description
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
看到这题的时候自己第一反应就是直接暴力解，两层循环嵌套，时间复杂度O(n2)
如下：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if(nums[i]+nums[j] == target):
return [i,j]
运行时间在倒数12.5%
第二种解法，Hash表，查找元素和映射之间关系最佳的方式就是用Hash，Python中直接采用内置dict
代码如下：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = {}
for i in range(len(nums)):
x = nums[i]
if target-x in dict:
return ([dict[target-x], i])
dict[x] = i
特别注意的坑是，不要先将所有元素放入dict中，因为dict必须每个键对应一个项，如果对应了多个，则后面的会顶替前面的元素。
超过89%的提交
