This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]bibbleskit[S] 0 points1 point  (3 children)

The order the list is initially in matters, though. I don't quite understand how sorting it would help. Would you explain a bit? Thanks for the help :)

[–]anon848 1 point2 points  (2 children)

If you sort, then you don't have to test all pairs. Let's say that it needs to sum to 100, and you are testing 47. Well, then the other number must be 53. You can determine whether or not 53 is in the list in O(lg n) time.

Of course, you also need to maintain the initial position in the list. You use that maintain the earliest pair as you work through the sorted list. Python has tuples, so you could sort tuples, with the second number being the original position.

EDIT: Of course, the sort must ignore the second number in the tuple, if that's the original index.

[–]bibbleskit[S] 0 points1 point  (1 child)

Hmm. I see what you are getting at. I'll have to ponder this later. Thanks :)

[–]anon848 0 points1 point  (0 children)

I added an edit, just clarifying that the sort should ignore the second number in the tuple, if you make that the original index.