Number of Subarray whose sum greater than given value

Question

Given an array of N integers (positive and negative), find the number of contiguous sub array whose sum is greater or equal to K (also, positive or negative)

I have managed to work out a naive O(N²) solution, is it possible to get better?

Answer 1

是的,有可能及时完成O(n log n).

1. 我们来看看前缀总和.一个(L, R]子阵列的总和是prefixSum[R] - prefixSum[L].

2. 这意味着我们可以算这样的数量L和R那个L < R和prefixSum[R] - prefixSum[L] >= K,这意味着prefixSum[L] <= prefixSum[R] - K.

3. 让我们从左到右迭代前缀和的数组,并维护一个可以有效地执行以下操作的数据结构:

   • 添加一个新元素.
   • 找到小于或等于给定数字的元素数.

   为此,我们可以使用平衡二叉搜索树.

以下是此解决方案的伪代码:

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).