Python different solutions (two-pointer, dictionary, binary search).


  • 39
    C
    # 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

  • 1
    T

    what is the time complexity of the binary search solution?


  • 1
    A

    @tommy1122337: O(n*log n)


  • 0
    D

    Here's a slightly modified version of the Python "dictionary" solution. It sets enumerate's second argument start=1 and adheres to EAFP instead of LBYL.

    def twoSum(self, numbers, target):
        """ two_sum == PEP8 """
        seen = {}
        for i, num in enumerate(numbers, 1):
            try:
                return [seen[num], i]
            except KeyError:
                seen[target - num] = i
    

  • 0
    H
    This post is deleted!

  • 0
    M

    cool solution!


  • 0
    G

    @delirious-lettuce ok,well,you solution is great,but you forget to plus 1 in your result:)


  • 4
    A

    Here's a summary of how long it takes to run for three methods:

    • Two pointers: 43 ms
    • Dictionary: 46 ms
    • Binary Search: 75 ms

    It was odd to me that binary search is significantly slower than other two methods; it should be faster since we are using the sorted feature. It turns out that if we don't repeat investigating the elements that have been already investigated, binary search becomes the fastest method. Here's the modified version which takes 35 ms:

    def twoSum(self, numbers, target):
        investigatedSoFar = []
        for i in range(len(numbers)):
            if not numbers[i] in investigatedSoFar:
                investigatedSoFar.append(numbers[i])
                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
    
    

  • 0
    S

    For the solution 1 and 2 , what will happen in this case?
    [1,2,2,2,3] target=3
    Should it return [1,2] or [1,4]? Since both solution will return the latter one, which one is correct?


  • 1
    M

    @tommy1122337 O(log(n))


  • 0
    M

    @sggkjihua your question is incorrect because the solution is unique per problem description


  • 0
    M

    @abbas2 nothing surprising, bst wins on long list


  • 0
    N

    @abbas2 but theoretically, two pointers is O(n) and binary search is O(n*log n)


Log in to reply
 

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