Why this solution does not work?


  • 0
    D

    Idea: for each i in array num, do a binary search in num for target - i in num.

    class Solution:
        # @return a tuple, (index1, index2)
    
        def binary_search(self, array, target):
            def _binary_search(a, l, h, t):
                if l == h:
                    return None
                elif a[(h + l) / 2] == t:
                    return (h + l) / 2
                elif a[(h + l) / 2] > t:
                    return _binary_search(a, l, (h + l) / 2, t)
                elif a[(h + l) / 2] < t:
                    return _binary_search(a, (h + l) / 2 + 1, h, t)
                else:
                    return None
    
            return _binary_search(array, 0, len(array) - 1, target)
    
        def twoSum(self, num, target):
            s_num = sorted(num)
            z_num = [(i, num.index(i)) for i in s_num]
            for tup in z_num:
                n = tup[0]
                i = tup[1]
                t = self.binary_search(s_num, target - n)
                if t != None:
                    index_2 = num.index(target - n)
                    if i == index_2:
                        index_2 = i + 1 + num[i:].index(target - n)
                    return (i + 1, index_2 + 1)
    

    Time complexity: n * log(n), uses extra space, not accepted, time expired.


Log in to reply
 

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