Python time limit problem


  • 0
    Y
    def twoSum(self, num, target):
        d = {}
        for i in range(len(num)):
            if num[i] in d.keys():
                return (d[num[i]]+1, i+1)
            else:
                d[target - num[i]] = i
    

    Why time limit exceeded in python? (Two sum problem)


  • 1
    Y

    I believe your code's time complexity is O(n^2), which will trigger time limit exceeded.


  • 0
    Y

    if I change "if num[i] in d.keys():" into "if d.has_key(num[i]):", I got accepted.


  • 0
    D

    i do what you said, it still report the bug


  • 0
    G

    the trick might be num[i] in d.keys(), the keys will be expanded, actually you should use num[i] in d, or d.has_key(num[i]), to see the differences, here: 'has_key()' or 'in'?


  • 2
    N

    list is different from dict,
    d.keys() returns the 'list' type and num[i] in a list got the O(n) time complexity,
    however,if num[i] in a dict got the O(1) time complexity


  • 1
    Z

    This code's time complexity is o(n^2), as you know, N will bigger than 16000, so this complexity is unacceptable. Just use sort and binary search, you can get o(nlogn).


  • 0
    L

    Another advantage to sorting is that you can easily ignore all of the values that cannot possibly sum to the target.


  • 0
    Z
    This post is deleted!

  • 0
    J

    Hi,I don't know whether you have solved it.I just tried to solve it today, and in the last,my codes got accepted with 172ms.
    the codes is here:

    def twoSum(self, num, target):

        dic={}
        for i in range(len(num)):
            sub=target-num[i]
            if sub in dic:
                return (dic[sub],i+1)
            else:
                dic[num[i]]=i+1
        return (-1,-1)
    

    Thanks all for the answers about the difference between "num[i] in d.keys()" and "d.has_key(num[i])".


  • 0
    A

    when you do
    if num[i] in d.keys():
    you are actually searching through a key list to see any match num[i]. Python's 'in' operator for list is O(N). therefore you get O(N^2) in total.


Log in to reply
 

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