Асимптотически оптимальный способ нахождения суммы трех элементов массива, ближайшего к заданному числу

Question

В своем ответе на на этот вопрос Джон Феминелла говорит:

Можно сделать это субквадратично, если вы действительно представляя каждое целое число как битовый вектор и выполняя быстрый Преобразование Фурье, но это выходит за рамки этого ответа.

Каков асимптотически оптимальный способ решения проблемы, описанной в этом вопросе?

Answer 1

Предположим, у нас есть массив 1 2 4.Мы представляем этот массив как многочлен f(x) = x^1 + x^2 + x^4.Давайте посмотрим на f(x)^2, то есть

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

Количество способов записать n как сумму двух элементов массива с коэффициентом x^n, и это в целом верно,БПФ дает нам способ эффективно умножать многочлены *, поэтому в основном мы вычисляем f(x)^3 и рассматриваем коэффициент целевого числа S.

• Причина, по которой этот алгоритм не решаетПроблема 3SUM состоит в том, что эффективность умножения FFT зависит от степени результирующего полинома и, таким образом, значения массива лежат в небольшом диапазоне.