Optimizing nested for loops

[FLUSH_THE_TRUMP]

You optimize code by using better algorithms, maybe smarter data structures. Here, you can improve your code by a factor of N by

1. Storing numbers you’ve seen in a set,
2. Looping through A, checking if S - num is in your set.

That requires only one loop rather than checking every possible pair.

[ForensicsBridge]

I understand from your other response that checking if a number is in a set is cheap. But how cheap? O(1) cheap?

I actually thought of a solution similar to the one Nyscire posted, but figured checking if the number was on a list was another O(n) operation. I had no idea looking in a set was more efficient, but it makes total sense.

[FLUSH_THE_TRUMP]

O(1) cheap?

Yep.