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

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 乘法的效率取决于生成的多项式的次数，因此数组值位于一个很小的范围内。