How can I optimize my Two Sums code in Python?

Question

I'm attempting the first problem on leetcode and my code passes the first 19 tests but fails due to a time exceeded failure on the last test. This is what I have so far:

class Solution:
    def twoSum(self, nums, target):
        k = 0
        n = len(nums)-1
        temp = []
        for x in range(k,n):
            for y in range(k+1,n+1):
                if (nums[x]+nums[y] == target) and (x < y):
                    temp.append(x)
                    temp.append(y)
                    break
        return temp

Please let me know if you have any information that you think could potentially help me. For those of you unfamiliar with the two sums problem. Here it is:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

I'm asking about the specifics about how to optimize MY code, not have other people write the code for me. Afterall, memorizing code won't do me any good if I don't know how to do it myself with my own thought processes. I'm asking for advice.

Personally, I'm not sure why you need the second for loop, and why you need (x — pyeR_biz, May 28 '18 at 17:41
Possible duplicate of [how to sum two number in a list?](https://stackoverflow.com/questions/49761846/how-to-sum-two-number-in-a-list) — Thierry Lathuille, May 28 '18 at 18:45
I'm asking how to optimize my code, not copy someone else's. The other post is simply other people writing code for the problem. — Classic Schmosby, May 28 '18 at 18:48
It seems that your code currently works, and you are looking to improve it. Generally these questions are too opinionated for this site, but you might find better luck at [CodeReview.SE](https://codereview.stackexchange.com/tour). Remember to read [their requirements](https://codereview.stackexchange.com/help/on-topic) as they are a bit more strict than this site. — AChampion, May 28 '18 at 19:03
@ClassicSchmosby you're welcome - note: I've also provided some guidance at the bottom of my answer below that may provide you what you need. — AChampion, May 28 '18 at 19:59
The main problem with your solution and the ones based on `itertools.combinations` is that that are O(n^2), as you basically test all possible combinations of two elements among n (there are n*(n-1)/2 combinations) until you find a valid one. When n is large, you will need a more efficient algorithm. One possibility is to first sort the list (this is O(n * log(n))), finding the solution is then only O(n), which gives you a solution in O(n * log(n)) globally. I explained it in more detail in my answer on the duplicate. You'll also find many optimization ideas in the other O(n^2) solutions. — Thierry Lathuille, May 29 '18 at 05:15

AChampion · Accepted Answer · 2018-05-28T19:15:11.547

You can probably speed things up a little bit using itertools, e.g.:

for i, j in it.combinations(range(len(nums)), r=2):
    if nums[i] + nums[j] == target:
        return [i, j]

Or alternatively:

for (i, x), (j, y) in it.combinations(enumerate(nums), r=2):
    if x+y == target:
        return [i, j]

An improvement to your code is in your second loop, to start from x+1 vs k+1, this removes the need for the and expression. And just immediately return vs. .append() which is relatively expensive. E.g.:

n = len(nums)-1
for x in range(0, n):
    for y in range(x+1, n+1):
        if nums[x]+nums[y] == target:
            return [x, y]

Loops in this structure is exactly what itertools.combinations() does.

score -1 · Answer 2 · answered May 28 '18 at 17:59

-1

Try this shortened version of the thing you are doing, this syntax is called 'list comprehension'

 def twoSum(nums, target):
        return [(x,x+1) for x in range(len(nums)-1) if nums[x]+nums[x+1] == target]

Here is a reference -

http://www.pythonforbeginners.com/basics/list-comprehensions-in-python

answered May 28 '18 at 17:59

pyeR_biz

986
12
36

I didn't downvote - but this doesn't answer the OP question as it is any 2 indexes not just 2 consecutive indexes, e.g. if `target = 13` then this returns nothing, when it should return `[0, 2]`. Also this returns a list of tuples, not just 2 indexes in a list. – AChampion May 28 '18 at 19:01
1

No indication in the question that the output needed is a list. When I posted my solution the question wasn't properly defined. There was just code, hence I asked the OP why the second for loop was needed. He stated the full question later. Thanks for not downvoting. – pyeR_biz May 29 '18 at 03:40

How can I optimize my Two Sums code in Python?

2 Answers2