LintCode Q56 Two Sum hash in Python

  • Jinhai ZHOU
  • 2 Minutes
  • 2016年11月17日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
"""
@param numbers : An array of Integer
@param target : target = numbers[index1] + numbers[index2]
@return : [index1 + 1, index2 + 1] (index1 < index2)
"""
def twoSum(self, numbers, target):
# write your code here
# list are not sorted
# worst case time O(n), space O(n)
targets = dict() # extra space O(n)
for i in xrange(len(numbers)):
if numbers[i] in targets:
return [targets[numbers[i]], i + 1]
else:
targets[target - numbers[i]] = i + 1
return [0, 0]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。