5个数字,使得它们的总和等于0

Question

给定5个大小为n的数组:a,b,c,d,e.有多少(i,j,k,g,h)就是这样的

a(i)+ b(j)+ c(k)+ d(g)+ e(h)= 0？

可以通过比O(n ^ 2 + n ^ 3)(使用哈希映射)更好的复杂性来解决这个问题吗？

Answer 1

如果数组包含有限大小的整数（即在 -u 到 u 范围内），那么您可以O(n+ulogu)通过使用快速傅里叶变换将每个集合的直方图卷积在一起来及时解决这个问题。

例如，该集合a=[-1,2,2,2,2,3]将由具有值的直方图表示：

ha[-1] = 1
ha[2]  = 4
ha[3]  = 1

将所有直方图与 FFT 进行卷积后，生成的直方图将包含条目，其中每个 bin 的值告诉您组合数字以获得每个可能总数的方式的数量。要找到总数为 0 的问题的答案，您所需要做的就是读取 bin 0 的直方图值。