3SUM

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

It is possible to solve the algorithm in O(n2) time using simple algorithms, and matching lower bounds are known for some specialized models of computation. Slightly faster randomized algorithms are known that exploit computational-model parallelism on a RAM and in the external-memory and cache-oblivious models (Baran, Demaine & Pǎtraşcu 2008). When the integers are in the range [−u ... u], 3SUM can be solved in time O(n + u lg u) by representing S as a bit vector, determining S + S by performing a discrete convolution using FFT, and then comparing to -S.

Quadratic algorithm

There is a simple algorithm to solve 3SUM in O(n²) time by first hashing each element in the array, finding all possible pairs, then finally checking for existence of the remaining value (which is simply the negative of the sum of each pair) using the hash table. Alternatively, the algorithm below first sorts the array, and then tests all possible pairs in a careful order that avoids the need to binary search for the pairs in the sorted list, again achieving O(n²) time.

Assume we have as input array S with elements S[0]..S[n-1]. Then the following algorithm will solve 3SUM problem in quadratic time.^[1]

sort(S); for i=0 to n-3 do a = S[i]; k = i+1; l = n-1; while (k<l) do b = S[k]; c = S[l]; if (a+b+c == 0) then output a, b, c; exit; else if (a+b+c > 0) then l = l - 1; else k = k + 1; end end end

Here is example how the above algorithm will find the result for some input (after it is sorted). Current values of a are shown in bold, values of b and c are shown in red.

-25 -10 -7 -3 2 4 8 10 (a+b+c==-25) -25 -10 -7 -3 2 4 8 10 (a+b+c==-22) . . . -25 -10 -7 -3 2 4 8 10 (a+b+c==-7) -25 -10 -7 -3 2 4 8 10 (a+b+c==-7) -25 -10 -7 -3 2 4 8 10 (a+b+c==-3) -25 -10 -7 -3 2 4 8 10 (a+b+c==2) -25 -10 -7 -3 2 4 8 10 (a+b+c==0)

[edit]

3SUM-hardness

A problem is called 3SUM-hard if solving it in subquadratic time implies a subquadratic-time algorithm for 3SUM. The concept of 3SUM-hardness was introduced by Gajentaan & Overmars (1995) in analysis of algorithms in computational geometry. By now there are a multitude of problems that fall into this category.