algorithm - 在整数数组中查找子数组和

Question

给定一个包含 N 个正整数的数组。它可以有 n*(n+1)/2 子数组，包括单元素子数组。每个子数组都有一个和 S。为所有子数组查找 S 显然是 O(n^2)，因为子数组的数量是 O(n^2)。许多和 S 也可以重复。有什么方法可以在 O(n logn) 中找到所有不同总和的计数(不是总和的确切值，而只是计数)。

我尝试了一种方法，但卡在了路上。我将数组从索引 1 迭代到 n。
假设 a[i] 是给定的数组。对于每个索引 i，a[i] 将添加到所有涉及 a[i-1] 的总和，并将包括其自身也作为单独的元素。但是如果在涉及a[i-1]的和中，两个和的差是a[i]，就会出现重复。我的意思是，假设总和 Sp 和 Sq 最终在 a[i-1] 并且两者的区别是 a[i ]。然后 Sp + a[i] 等于 Sq，将 Sq 作为副本。

假设 C[i] 是不同总和的计数，其中最终在 a[i]。
所以 C[i] = C[i-1] + 1 - 涉及 a[i-1] 且差为 a[i] 的和数对。

但问题是在O(log n) 中找到对数的部分。请给我一些提示，或者如果我走错了路并且需要完全不同的方法，请指出问题。

Answer 1

当 S 不太大时，我们可以用一次(快速)多项式乘法计算不同的和。当 S 较大时，N 有望小到足以使用二次算法。

令 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}) 的乘积； k > 0 的 z^k 的系数非零当且仅当 k 是子数组和，所以我们只需要读出正幂的非零系数的数量。此外，z 的幂范围从 -S 到 S，因此乘法所需的时间约为 S log S。