LintCode Q56 Two Sum sort in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年11月17日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 complextiy: O(nlogn)
# O(1) space
numbers = sorted(enumerate(numbers), key=lambda x: x[1]) # O(nlogn)
lo = 0
hi = len(numbers) - 1
while lo < hi:
val = numbers[lo][1] + numbers[hi][1]
if val == target:
lo_indice = numbers[lo][0] + 1
hi_indice = numbers[hi][0] + 1
if lo_indice > hi_indice:
lo_indice, hi_indice = hi_indice, lo_indice
return [lo_indice, hi_indice]
elif val > target:
hi -= 1
else:
lo += 1
return [0, 0]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。