寻找数组中三个元素的和最接近给定数字的渐进最优方法

Question

在回答这个问题时，John Feminella说道：

如果你变得很聪明地将每个整数表示为一个位向量并执行快速傅里叶变换，则可以在次二次时间内完成此操作，但这超出了此答案的范围。

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

- Yktula

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

- foo

---

f(x)^3有O(n^3)个系数。FFT能让你计算出一些有用的系数子集吗？ - Tom Sirgedas

看起来这个程序可以检测三个数字的总和是否等于给定的目标，但它不能找出这三个数字是什么。我对此有误解吗？ - templatetypedef

@foo- 你会怎么做呢？我不知道这些调用看起来是什么样子的。 - templatetypedef

一个简单的随机化策略是尝试子序列，其中每个元素独立地以1/2的概率被包含。三个目标元素都以恒定的概率被包含，而其他元素中预期有恒定比例的元素会消失。我相信这可以被去随机化，但我手头没有引用。 - foo

@templatetypedef 参见此链接以了解如何恢复解决方案。http://cstheory.stackexchange.com/questions/32036/finding-witness-in-minkowski-sum-of-integers/32196 - Chao Xu