6

给定一个包含 N 个正整数的数组。它可以有n*(n+1)/2子数组，包括单元素子数组。每个子数组都有一个 sum S。查找S's所有子数组显然O(n^2)是子数组的数量O(n^2)。许多总和S's也可以重复。有没有办法在O(n logn).

我尝试了一种方法，但卡在了路上。我将数组从索引 1 迭代到 n。
Saya[i]是给定的数组。对于每个 index i，a[i]将添加到所a[i-1]涉及的所有总和中，并将其自身也作为单个元素包含在内。但是，如果在a[i-1]所涉及的总和中，两个总和的差为 ，则会出现重复a[i]。我的意思是，说总和Sp并以两者之差Sq结束。然后等于，作为副本给出。a[i-1]a[i]Sp + a[i]SqSq

SayC[i]是最终在 的不同总和的计数a[i]。
所以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)。请给我一些提示，或者如果我走错路并且需要完全不同的方法，请指出这一点。

4

2 回答 2

10

当 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 是子数组和时，k > 0 的 z^k 的系数是非零的，因此我们只需读取正幂的非零系数的数量。此外，z 的幂在 -S 到 S 的范围内，因此乘法需要 S log S 量级的时间。

于 2013-07-07T00:10:06.300 回答
0

您可以将子数组视为一种树。从某种意义上说，子数组[0,3]可以分为[0,1]和[2,3]。

因此，构建一棵树，其中节点由子数组的长度定义，并且它在原始数组中的起始偏移量，并且每当您计算子数组时，将结果存储在这棵树中。

计算子数组时，您可以检查此树以获取现有的预计算值。

此外，在划分时，如果这很重要，可以在不同的 CPU 内核上计算数组的某些部分。

此解决方案假定您不需要同时需要所有值，而是临时需要。对于前者，可能有一些更聪明的解决方案。

另外，我假设我们正在谈论 10000 甚至更多的元素计数。否则，这样的工作是一个很好的练习，但没有太大的实用价值。

于 2013-07-07T00:34:03.613 回答