两数之和（leetcode一百复盘）

1.两层循环，暴力

找当前的i对应的j，且i！=j

2.哈希数组

存一遍哈希数组（python里面字典实现），注意字典的键和值只能有一对

第一种：先存一边数组，然后比对

class Solution(object):

def twoSum(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: List[int]

"""

hash_map={}

for i,value in enumerate(nums):

hash_map[value]=i

for i,value in enumerate(nums):

need=target-value

if need in hash_map and hash_map[need]!=i:

return [i,hash_map[need]]

时间复杂度略高于下一种

特殊案例：

注意第二次存储3的时候字典的值会覆盖第一次的，但是能搜索到，可能算3数之和的时候就不行了

第二种：边存储边读取

class Solution(object):

def twoSum(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: List[int]

"""

hash_map={}

for i,value in enumerate(nums):

need=target-value

if need in hash_map:

return [hash_map[need],i]

hash_map[value]=i

先看前面存了需要的值没有，再存储目前的值，只需要一个循环