(python实现)两数之和
2021-11-02 本文已影响0人
JLGao的简书
问题描述
给出一个整型数组 和一个目标值,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。数据范围: ,,。
例如:给出的数组为 , 目标值为,返回一个数组,因为
class Solution:
# write code here
def paritition(self, alist, left, right):
key = alist[left]
while left < right:
if left < right and key <= alist[right]:
right = right - 1
alist[left] = alist[right]
if left < right and alist[left] <= key:
left = left + 1
alist[right] = alist[left]
alist[left] = key
return left
def Qsort(self, alist, left, right):
piviots = [(left, right)]
while len(piviots) > 0:
piviot = piviots.pop(0)
if piviot[0] < piviot[1]:
piviot_num = self.paritition(alist, piviot[0], piviot[1])
if piviot_num - 1 > piviot[0]:
piviots.append((piviot[0], piviot_num-1))
if piviot_num + 1 < piviot[1]:
piviots.append((piviot_num+1, piviot[1]))
def twoSum(self , numbers , target ):
# write code here
res = [0,0]
if len(numbers)<2:
return res
num = list(numbers)
self.Qsort(num,0,len(numbers)-1)
i,j = 0,len(num)-1
while i<j:
while num[i]+num[j]<target:
i+=1
while num[i]+num[j]>target:
j-=1
if num[i]+num[j]==target:
break
if num[i]+num[j]==target:
if num[i]!=num[j]:
res[0] = min(numbers.index(num[i]),numbers.index(num[j]))+1
res[1] = max(numbers.index(num[i]),numbers.index(num[j]))+1
else:
idx = [k for k,x in enumerate(numbers) if x==num[i]]
res[0] = idx[0]+1
res[1] = idx[1]+1
return res
if __name__=='__main__':
while True:
try:
s = input().replace('[', '').replace(']', '').split(',')
numbers = list(map(int,s[:-1]))
target = int(s[-1])
A = Solution()
res = A.twoSum(numbers, target)
print(res)
except:
break
时间复杂度:
空间复杂度: