arrays - 找到最接近给定数字的数组的三个元素之和的渐近最优方法

Question

在他对 this question 的回答中, John Feminella 说:

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.

解决该问题中描述的问题的渐近最优方法是什么？

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的系数，一般情况下都是这样。 FFT 为我们提供了一种有效乘以多项式的方法*，因此基本上我们所做的是计算 f(x)^3 并查看目标数 S 的系数。

• 此算法无法解决 3SUM 问题的原因是 FFT 乘法的效率取决于所得多项式的次数，因此数组值位于一个很小的范围内。