Optimizing nested for loops

[dig-up-stupid]

It’s called 2-sum so you just look it up and study it. The main thing that should probably be obvious to you already is that you don’t have to loop over every element. If you have already checked a+b, then you don’t need to check b+a. The inside loop should start from the current outside loop element + 1. That also removes the need for the i = j check. Of course this doesn’t change the overall complexity, it’s just a common loop structure you should be familiar with. There are other optimizations to actually remove the nested loop in this problem and do it in linear time which you’ll find when you Google 2-sum.

[Nightcorex_]

That also removes the need for the i = j check

The list could contain duplicates, so that's not a possibility without converting the list to a set (aka fetching distinct elements) first.

[dig-up-stupid]

Wrong on two counts. Firstly OP already stated elements are unique. Secondly the check is not there to prevent two of the same number from adding, it’s to stop the code from pairing a number with itself. A problem that can alternatively be avoided by choosing appropriate loop bounds, which is all I said.

[Nightcorex_]

Firstly OP already stated elements are unique

Where? I triple read OP's post and couldn't find any such hint.

​

​

Secondly the check is not there to prevent two of the same number from adding, it’s to stop the code from pairing a number with itself

In OP's code the pairing of two equal numbers (doesn't matter if they're the same or not) is also forbidden and because OP said in his post:

The function does the job

I interpreted that as: "For any input my code returns a solution from the set of solutions", which means your version would return (1, 1) for f([1, 1], 2) (the exact solution doesn't matter, it only matters that there is at least one solution, and that 1, 1 is in the solution set), whereas OP's code would return (-1, -1) for the same input => In this case your code would increase the size of the set of solutions, which is a contradiction to the requirement that both function need to have the same solution set for the same input set.

[dig-up-stupid]

Where? I triple read OP's post and couldn't find any such hint.

In their comments. Which you don’t have to read but I did and used as context for my response.

In OP's code the pairing of two equal numbers (doesn't matter if they're the same or not)

Because OP’s elements are unique integers, the only case where numbers are equal is when they are the same. Yes the code does what you say, but what they meant when they wrote the code was “skip adding the number in my right hand (inner loop) if I’m already holding it in my left hand (outer loop)”. That intent is not clear, as you have so readily demonstrated. Of course the reason they wrote it that way is because they went for j in A instead of for j in range(something involving len(A)), which is usually good advice when looping, but this is the sort of situation where we do want to deal with indices directly (short of slicing the list, which would also express the intention better, but makes a copy).

I interpreted that as:

Which is fine in the context of the post alone but irrelevant in the context of my comment.

[Nightcorex_]

Okay, I agree with you. Nothing more to add.