python - 清晰图解 - 字典模拟 哈希表 - 两数之和 - 只需遍历一次 数组
两数之和
http://www.nowcoder.com/questionTerminal/20ef0972485e41019e39543e8e895b7f
谁说一定要全部建立好hashMap以后才能开始查找呢？
大家可以观察一下，以下的代码~
上代码
（python3）
class Solution:
def twoSum(self, numbers, target):
# write code here
if len(numbers) > 1:
return self.getHash_traverseOnce(numbers, target)
else:
return []
def getHash_traverseOnce(self, numbers, target):
hashMap = {}
for _ in range(len(numbers)):
remainder = target - numbers[_]
if remainder in hashMap:
'''+1 是因为返回的index 要求从1开始'''
return [hashMap[remainder]+1, _+1]
else:
hashMap[numbers[_]] = _
return [] 思路简介
1. 只需遍历一次原数组
2. 没必要等到 建立完整的hashMap再查找，我们可以边查边找，找到了就不继续建立咯！
思路2最大的特性就是：
- 我们每次 插入一个新的数 进入hashMap， 我们在插入之前，就看看他的补数remainder是不是已经在数组里了？
- 如果在的话，直接返回结果。
- 如果不在的话，就正常插入，毕竟，咱们不能排除这个数可能是，后来还没插入数的补数的可能性。
思路图解
图解， target=40 为例！
初始化：
- 准备插入 key= 20 & index=0， remainder = 40 - 20 = 20，而 20此时并不在hash map里，正常插入 key=20, index = 0
2. 准备插入 key= 30 & index=1， remainder = 40 - 30 =10， 10 并不在hash map里，正常插入 key=10, index =1
3. 准备插入 key= 20 & index=2， remainder = 40 - 20 =20， 而 20此时已经有一个存在在hash map里，说明找到了 remainder = 20， index=0！
那现在就停止插入key= 20 & index=2，因为已经找到啦他的补数 remainder = 20， index=0 啦~可以返回啦
return [ remainder的index=0+1, 当前数的index=2+1]
（+1 是因为要求返回的index 从1开始）
题外话，大家可以去我的博客看看我的小笨方法 我的笨博客 ，一起探讨~
