# Time Limit Exceeded with my python code

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

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

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

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

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

• This post is deleted!

• This post is deleted!

• That makes sense. Thanks dude!

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