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

Question

John Feminella 在回答这个问题时说:

如果您真的很喜欢,可以通过将每个整数表示为位向量并执行快速傅立叶变换来实现这种子二次方,但这超出了本答案的范围.

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

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的效率乘以取决于所得多项式的程度,因此阵列值位于小范围内.