给定一个数组N整数（正数和负数），找出连续的总和大于或等于的子数组K（也可以是正数或负数）
I have managed to work out a naive O(N2) solution, is it possible to get better?
是的，可以在O(n log n) time.
让我们看一下前缀和。总和一个(L, R]子数组是prefixSum[R] - prefixSum[L].
这意味着我们可以计算这样的数量L and R that L < R and prefixSum[R] - prefixSum[L] >= K， 意思是prefixSum[L] <= prefixSum[R] - K.
-
让我们从左到右迭代前缀和数组，并维护一个可以有效执行以下操作的数据结构：
- 添加一个新元素。
- 查找小于或等于给定数字的元素数量。
为此，我们可以使用平衡二叉搜索树。
这是该解决方案的伪代码：
tree = an empty search tree
result = 0
// This sum corresponds to an empty prefix.
prefixSum = 0
tree.add(prefixSum)
// Iterate over the input array from left to right.
for elem <- array:
prefixSum += elem
// Add the number of subarrays that have this element as the last one
// and their sum is not less than K.
result += tree.getNumberOfLessOrEqual(prefixSum - K)
// Add the current prefix sum the tree.
tree.add(prefixSum)
print result
时间复杂度为O(n log n)因为有O(n)添加和计算元素数量操作，每个操作都可以在O(log n).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
