61 lines
1.6 KiB
Python
61 lines
1.6 KiB
Python
def twoSum(numbers, target):
|
|
"""
|
|
:type numbers: List[int]
|
|
:type target: int
|
|
:rtype: List[int]
|
|
"""
|
|
if target >= 0:
|
|
last = len(numbers)-1
|
|
else:
|
|
last = 1
|
|
# print( last)
|
|
while last > 0:
|
|
if numbers[last] > target and target > 0:
|
|
for i in range(len(numbers)):
|
|
last -= 1
|
|
if numbers[last] < target:
|
|
break
|
|
for x in range(len(numbers)):
|
|
if numbers[x] + numbers[last] == target:
|
|
return [x+1, last+1]
|
|
if target >= 0:
|
|
last -= 1
|
|
else:
|
|
last += 1
|
|
# # two-pointer
|
|
# def twoSum1(self, numbers, target):
|
|
# l, r = 0, len(numbers)-1
|
|
# while l < r:
|
|
# s = numbers[l] + numbers[r]
|
|
# if s == target:
|
|
# return [l+1, r+1]
|
|
# elif s < target:
|
|
# l += 1
|
|
# else:
|
|
# r -= 1
|
|
|
|
# # dictionary
|
|
# def twoSum2(self, numbers, target):
|
|
# dic = {}
|
|
# for i, num in enumerate(numbers):
|
|
# if target-num in dic:
|
|
# return [dic[target-num]+1, i+1]
|
|
# dic[num] = i
|
|
|
|
# # binary search
|
|
# def twoSum(self, numbers, target):
|
|
# for i in xrange(len(numbers)):
|
|
# l, r = i+1, len(numbers)-1
|
|
# tmp = target - numbers[i]
|
|
# while l <= r:
|
|
# mid = l + (r-l)//2
|
|
# if numbers[mid] == tmp:
|
|
# return [i+1, mid+1]
|
|
# elif numbers[mid] < tmp:
|
|
# l = mid+1
|
|
# else:
|
|
# r = mid-1
|
|
|
|
print(twoSum([2,7,11,15], 9))
|
|
print(twoSum([-1,0], -1))
|
|
# print(twoSum([5,25,75], 100)) |