# Python time limit problem

• ``````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)

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

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

• i do what you said, it still report the bug

• 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'?

• 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

• 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).

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

• This post is deleted!

• 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])".

• 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.

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