1. Two Sum
Feb 23, 2017 · 1 min read
Everyone talks about 2Sum…Haha.
Way 1
This is somehow a searching problem, simply try all possible solution pairs. O(n²).
Way 2
Try some reductions. Reduce 2Sum to 1Sum. For a[k], can we find its companion in A[0, k)？The search cost O(n), or O(logn), or even O(1). That’s it.
Way 3
Sorting always helps searching. What if the input is sorted. Use recursion. For A[0, n), can we reduce its dimension? Would A[0] be in the answer? If A[0] + A[n-1] < target, then A[0] is not the answer, reduce to A[1, n). If A[0] + A[n-1] > target, then A[n-1]) is not the answer, reduce to A[0, n-1).
O(n).
