给定一个包含 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]
Sq
Sq
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)
。请给我一些提示,或者如果我走错路并且需要完全不同的方法,请指出这一点。