Asymptotically optimal way to find the sum of three elements of an array closest to a given number

Question

In his answer to this question, John Feminella says:

It's possible to do this sub-quadratically if you get really fancy, by representing each integer as a bit vector and performing a fast Fourier transform, but that's beyond the scope of this answer.

What is the asymptotically optimal way of solving the problem described in that question?

Answer 1

Suppose we have an array 1 2 4. We represent this array as a polynomial f(x) = x^1 + x^2 + x^4. Let's look at f(x)^2, which is

x^2 + 2 x^3 + x^4 + 2 x^5 + 2 x^6 + x^8

The number of ways to write n as the sum of two elements of the array is the coefficient of x^n, and this is true in general. FFT gives us a way to multiply polynomials efficiently*, so basically what we do is compute f(x)^3 and look at the coefficient of the target number S.

• The reason this algorithm doesn't solve the 3SUM problem is that the efficiency of an FFT multiply depends on the degree of the resulting polynomial and thus that the array values lie in a small range.