Fast Fourier transform
When the elements are integers in the range formula_10, 3SUM can be solved in formula_11 time by representing the input set formula_12 as a bit vector, computing the set formula_13 of all pairwise sums as a discrete convolution using the Fast Fourier transform, and finally comparing this set to formula_14.