给定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)更好的复杂性(使用哈希映射)解决此问题？
最佳答案
如果数组包含有限大小的整数(即在-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的直方图的值。
关于algorithm - 5个数字，使得它们的总和等于0，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25459128/