Time Limit Exceeded with my python code


  • 1
    L

    It seems the code runs at very slow speed. Any suggestions to speed it up would be appreciated.

    class Solution:
        # @return a tuple, (index1, index2)
        def twoSum(self, num, target):
            for num1 in num:
                if num.count(target-num1)>0:
                    if target-num1!=num1:
                        return (num.index(num1),num.index(target-num1))
                    else:
                        if num.count(target-num1)>1:
                            indices = [i for i, x in enumerate(num) if x == num1]
                            return(indices[0],indices[1])
    

    Basically I scanned through the list. each time, check the existence of target-num1.

    Also if target-num1== num1, the code will make sure they do not have the same indexes.

    Thank you for your attention


  • 2
    C

    Here's my solution :

    class Solution:
        # @return a tuple, (index1, index2)
        def twoSum(self, num, target):
            d = {n:pos for pos,n in enumerate(num) }
            for i,n in enumerate(num):
                if d.get(target-n):
                    return (i+1, d[target-n]+1)
            return None

  • 0
    L

    Thanks for sharing your answer. A quick question, what if there are duplicates in num. for example, when target =2 and there is at least one element with value of 2. Will the code give undesired solution?

    Thanks again!


  • 0
    C

    My solution won't deal with duplicates. In such case, the index kept in dictionary d is undefined. I expected it to keep the position of last seen number.

    In [18]: s.twoSum( [ 2, 2, 0, 1, 5, 6, 0, 3], 2)
    Out[18]: (1, 7)

    In above case we get first 2, but not the first 0. I am not sure why.


  • 0
    C

    Looking for target-num1 through a linear scan (I am guessing .count()) is linear ) is what's causing you the problem. If you put them in a dict look-up time is constant.


  • 0
    C
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    L

    That makes sense. Thanks dude!


Log in to reply
 

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