My accepted python code


  • 0
    V

    Since target = i + (target - i) , you can select one element and see if any other element which can be combined target.

    You can use the following code to do the search, but this will take linear time to do so, which will exceed the time limit in this problem.

    for i in range(len(num)):
        if not target - num(i) in num:
    

    Therefore, using dictionary for search is the alternative way, which only take constant time for search.

    The full code as below,

    class Solution:
        # @return a tuple, (index1, index2)
        def twoSum(self, num, target):
            dict_num = dict()
            for i in num:
                dict_num[i] = 1
    
            for i in range(len(num) - 1):
                if not target - num[i] in dict_num:
                    continue
                for j in range(i + 1, len(num)):
                    if num[i] + num[j] == target:
                        return i + 1, j + 1
    

    Well... I don't know how to estimate the time complexity yet.
    Is it O(n) or O(nlogn)?


  • 0
    L
    class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        dict_num = dict.fromkeys(num,0)
        for i in range(len(num) - 1):
            if not target - num[i] in dict_num:
                continue
            try :
                return i + 1, i+2+num[i+1:].index(target - num[i])
            except :
                continue
    

    With your help, I finally AC this problem.And here is my version.And below is another one,also using dict(), but slower:

    class Solution :
        def twoSum(self,num,target):
            Dic = dict()
            n = 1
            for i in num :
                Dic[i] = n
                n += 1
            Len = len(num) + 1
            while True:
                Len -= 1
                A = num.pop()
                try :
                        B = Dic[target - A]
                        if Len == B : continue
                        C = [Len,B]
                        C.sort()
                        return tuple(C)
                except :
                        continue

Log in to reply
 

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