26 Dec 2011
Given an array a ... a[n-1], find 2 elements that sum up to k
Now this is a classic problem. Everybody will certainly say it is O(n^2).
It turns out that there is a O(n log n) solution.
First of all, sort the array. Next, we put pointer p at a and pointer q at a[n-1].
Let's try every possible case:
Now let's see some proof.
If a[p] + a[q] > k, then a[p+i] + a[q] is always greater than k. Therefore, q will never be part of the answer.
If a[p] + a[q] < k, then a[p] + a[q-i] is always less than k. Therefore, p will never be the answer.
And that's it.