Linear time algorithm for 2-SUM

Given that the array is sorted (WLOG in descending order), we can do the following: Algorithm A_1: We are given (a_1,...,a_n,m), a_1<...,<a_n. Put a pointer at the top of the list and one at the bottom. Compute the sum where both pointers are. If the sum is greater than m, move the above pointer down. If the sum is less than m, move the lower pointer up. If a pointer is on the other (here we assume each number can be employed only once), report unsat. Otherwise, (an equivalent sum will be found), report sat.

It is clear that this is O(n) since the maximum number of sums computed is exactly n. The proof of correctness is left as an exercise.

This is merely a subroutine of the Horowitz and Sahni (1974) algorithm for SUBSET-SUM. (However, note that almost all general purpose SS algorithms contain such a routine, Schroeppel, Shamir (1981), Howgrave-Graham_Joux (2010), Becker-Joux (2011).)

If we were given an unordered list, implementing this algorithm would be O(nlogn) since we could sort the list using Mergesort, then apply A_1.

The classic linear time two-pointer solution does not require hashing so can solve related problems such as approximate sum (find closest pair sum to target).

First, a simple n log n solution: walk through array elements a[i], and use binary search to find the best a[j].

To get rid of the log factor, use the following observation: as the list is sorted, iterating through indices i gives a[i] is increasing, so any corresponding a[j] is decreasing in value and in index j. This gives the two-pointer solution: start with indices lo = 0, hi = N-1 (pointing to a[0] and a[N-1]). For a[0], find the best a[hi] by decreasing hi. Then increment lo and for each a[lo], decrease hi until a[lo] + a[hi] is the best. The algorithm can stop when it reaches lo == hi.