鉴于N个​​正整数数组。它可以有 N *（N + 1）/ 2 子阵列包括单元素的子阵列。每个子阵列具有总和取值。找到的s 的所有子阵列显然是为O（n ^ 2）作为子阵列的数量为O（n ^ 2）。许多款项的s 可以重复也。有没有什么办法可以找到所有不同的总和（不和的精确值，但只能算）计数为O（n LOGN）。

Given an array of N positive integers. It can have n*(n+1)/2 sub-arrays including single element sub-arrays. Each sub-array has a sum S. Find S's for all sub-arrays is obviously O(n^2) as number of sub-arrays are O(n^2). Many sums S's may be repeated also. Is there any way to find count of all distinct sum (not the exact values of sums but only count) in O(n logn).

我尝试过的方法，但卡在路上。我迭代从索引1的阵列到n。 说 A [1] 是给定的数组。对于每个指数我， A [1] 将添加到所有款项，其中 A [I-1] 参与，也将包括自身作为单独的元件。但是，重复的会出现，如果总和之中，其中 A [I-1] 参与，两个和的区别是 A [1] 。我的意思是，说款项 SP 和广场结束在 A [I-1] 两者的区别在于 A [1] 。然后 SP + A [1] 等于广场，使广场作为重复。

I tried an approach but stuck on the way. I iterated the array from index 1 to n. Say a[i] is the given array. For each index i, a[i] will add to all the sums in which a[i-1] is involved and will include itself also as individual element. But duplicate will emerge if among sums in which a[i-1] is involved, the difference of two sums is a[i]. I mean that, say sums Sp and Sq end up at a[i-1] and difference of both is a[i]. Then Sp + a[i] equals Sq, giving Sq as a duplicate.

说 C [I] 是截然不同的款项中，最终在 A [1] 的数量。 所以 C [I] = C [I-1] + 1 - 双款项，其中[I-1]是参与其差值的数量是A [1]

Say C[i] is count of the distinct sums in which end up at a[i]. So C[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i].

但问题是要找到对的数量在 O（log n）的部分。请给我一些暗示这个，或者如果我在错误的道路完全不同的方法是必需的问题点出来。

But problem is to find the part of number of pairs in O(log n). Please give me some hint about this or if I am on wrong way and completely different approach is required problem point that out.

推荐答案

当S是不是太大，我们可以统计不同的款项有一个（快）多项式乘法。当S是较大的，N是希望小到足以用二次算法。

When S is not too large, we can count the distinct sums with one (fast) polynomial multiplication. When S is larger, N is hopefully small enough to use a quadratic algorithm.

让X_1，X_2，...，x_n是数组元素。让y_0 = 0和y_i = X_1 + X_2 + ... x_i。令P（Z）= Z ^ {y_0} + Z ^ {Y_1} + ... + Z ^ {y_n}。计算多项式P（z）的产品* P（z ^ { - 1}）; Z 2 K的K> 0的系数为非零当且仅当k是子阵列求和，所以我们只需要读出的阳性权力非零系数的数目。 z的权力，而且，范围-S到S，所以乘花费时间S日志S的顺序。

Let x_1, x_2, ..., x_n be the array elements. Let y_0 = 0 and y_i = x_1 + x_2 + ... + x_i. Let P(z) = z^{y_0} + z^{y_1} + ... + z^{y_n}. Compute the product of polynomials P(z) * P(z^{-1}); the coefficient of z^k with k > 0 is nonzero if and only if k is a sub-array sum, so we just have to read off the number of nonzero coefficients of positive powers. The powers of z, moreover, range from -S to S, so the multiplication takes time on the order of S log S.