（python实现）两数之和

问题描述

给出一个整型数组 和一个目标值，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。数据范围： ，，。

例如：给出的数组为 , 目标值为，返回一个数组，因为

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

时间复杂度：
空间复杂度：