I would sort the list and create a break condition in the innermost loop. When a sum bigger than k is observed there is no point in continuing on testing said number of the outer loop.
If we sort the list first, I can do you one better: have two iterators/indices, i at the start and j at the end. If the sum of the pointees is k, return true. If it is less, increment i. If it is more, decrement j. If i and j meet (and the sum did not equal k), return false. This is O(n).
I would sort the list and create a break condition in the innermost loop. When a sum bigger than k is observed there is no point in continuing on testing said number of the outer loop.
If we sort the list first, I can do you one better: have two iterators/indices, i at the start and j at the end. If the sum of the pointees is k, return true. If it is less, increment i. If it is more, decrement j. If i and j meet (and the sum did not equal k), return false. This is O(n).
Unfortunately sorting the list is O(n log(n)).
Good point. I forgot that sorting is expensive