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 ia[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 回答