塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-167两数之和II

最初想法:

遍历,固定第一个数,用target减去此数,在list中查找差是否存在。但未利用到数组有序的条件。

Method2:

两层循环,超时了,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def twoSum(numbers, target):
for i in range(len(numbers)):
for j in range(i+1,len(numbers)):
if numbers[i] + numbers[j] > target:
break
if numbers[i] + numbers[j] == target:
return [i+1,j+1]
改进:遇到sum<target且相同的元素就跳过,还是超时
def twoSum(numbers, target):
for i in range(len(numbers)):
temp = None
for j in range(i+1,len(numbers)):
if temp == numbers[j]:
continue
if numbers[i] + numbers[j] < target:
temp = numbers[j]
elif numbers[i] + numbers[j] == target:
return [i+1,j+1]
else:
break
return None

题解:双游标,分别执行开头和末尾,sum>target,开头的游标后移,sum<target,末尾游标前移。

最终版

1
2
3
4
5
6
7
8
9
10
11
12
13
def twoSum(numbers, target):
firstpoint = 0
lastpoint = len(numbers)-1
while firstpoint<lastpoint:
mysum = numbers[firstpoint]+numbers[lastpoint]
if mysum == target:
return [firstpoint+1,lastpoint+1]
if mysum > target:
lastpoint -= 1
else:
firstpoint += 1
return None
print(twoSum([3,24,50,79,88,150,345],200))
if help:小手一抖点个广告 or 大手一挥资助一下