一种在O(nlog(n))时间内求0的数组求和项的算法

Question

我正在处理以下问题：

设A是长度为n的数组，每个元素为-10n，<=，Ai，<=，10n。创建一个在O(nlog(n))时间内运行的算法，该算法确定是否存在条目Ai、Aj和AK，从而使Ai + Aj + Ak = 0。

我正以下面的方式接近它。定义n-1次多项式p，使x^k项上的系数为Ak。然后用使用FFT乘法p本身，然后再用p乘以得到的多项式，如果得到的多项式中的任何系数为0，则返回true。否则，返回假。由于FFT是O(nlog(n))，那么这个算法就是O(nlog(n))。

我遇到的问题是FFT结合了类似的术语。因此，系数0的存在并不意味着这类条目的存在。

有人能建议修改这个算法来改进它吗？

Answer 1

如果我没记错的话，解决这个问题的方法是：

1. 定义一个度60n + 1多项式，其中x^k项上的系数是数组中出现的元素k - 10n的次数。例如，如果是n=8，则x^5上的系数是-75 (-75 = 5 - 10x8)出现的次数。
2. 使用快速傅立叶变换将(60n + 1度的)多项式提高到三次方。
3. 看看x^(30n)上的系数是否为非零。如果是的话，就有答案了。

下面是python上的一个示例实现，它似乎适用于我提出的所有案例：

import numpy as np
from numpy.fft import fft, ifft

def hasZeroSum(a):
    n = len(a)
    b = [0 for x in range(n * 60 + 1)]
    for el in a: b[el + 10 * n] += 1
    f = fft(b, n * 60 + 1)
    f = np.power(f, 3)
    res = ifft(f, n * 60 + 1)
    return np.absolute(res[n * 30]) > 0.5

print hasZeroSum([-11, -5, 2, 3, 7])
print hasZeroSum([-11, -5, 2, 4, 8])

打印

True
False