arrays - 在这些条件下，是否有可能比 O(n^2) 更好地执行 3-sum/4-sum...k-sum？ - 技术面试

Question

这是一个经典问题，但我很好奇是否有可能在这些条件下做得更好。

问题:假设我们有一个长度为4*N的排序数组，即每个元素重复4次。请注意，N 可以是任何自然数。此外，数组中的每个元素都受制于 0 < A[i] < 190*N 的约束。数组中是否有 4 个元素使得 A[i] + A[j] + A[k] + A[m] = V，其中 V 可以是任何正整数；请注意，我们必须恰好使用 4 个元素，并且它们可以重复。不一定要求找到满足条件的 4 个元素，而是仅显示它可以对给定的数组完成并且 V 就足够了。

例如:A = [1,1,1,1,4,4,4,4,5,5,5,5,11,11,11,11]V = 22

这是真的，因为 11 + 5 + 5 + 1 = 22。

我的尝试:

我首先尝试了 k-sum 而不是“4sum”，但事实证明这非常困难，所以我转而采用了这种变体。我想到的第一个解决方案是相当幼稚的 O(n^2)。然而，考虑到这些限制，我想我们可以做得更好。我尝试了一些动态编程方法和分而治之，但这并没有让我有任何进展。具体来说，我不确定如何以一种可以“消除”数组部分而不必针对所有或几乎所有排列显式检查值的方式巧妙地处理这个问题。

Answer 1

1. 制作一个长度为256N的向量S0，其中S0[x]=1如果x出现在< strong>A.
2. 执行 S0 与自身的卷积以生成长度为 512N 的新向量 S1。 S1[x] 非零当且仅当 x 是 A 中 2 个数的和。
3. 执行S1 与自身的卷积以生成新向量S2。 S2[x] 非零当且仅当 x 是 A 中 4 个数的和。
4. 检查 S2[V] 以获得答案。

可以使用 FFT 卷积 (http://www.dspguide.com/ch18/2.htm) 或类似技术在 O(N log N) 时间内执行卷积。

由于最多执行 4 个这样的卷积，因此总复杂度为 O(N log N)