Python solution with dictionary and binary search


  • 0
    G

    First, find out the position of target/2, and start search in two directions.
    '''
    class Solution(object):

    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic={}
        k=self.getPosition(numbers, target/2)
        print k
        for i in range(k,-1,-1):
            if target-numbers[i] not in dic:
                dic[numbers[i]]=i
            else:
                return [i+1, dic[target-numbers[i]]+1]
            if 2*k-i < len(numbers):
                if (target-numbers[2*k-i]) not in dic:
                    dic[numbers[2*k-i]]= 2*k-i
                else:
                    return [2*k, dic[target-numbers[2*k-i]]+1]
        
    def getPosition(self, numbers, n):
        i=0
        j=len(numbers)-1
        while i<j+1:
            if numbers[(i+j)/2]<n:
                i=(i+j)/2
            elif numbers[(i+j)/2]>n:
                j=(i+j)/2
            return j
    

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.