总和大于给定值的子数组数 [英] Number of Subarray whose sum greater than given value

问题描述

给出一个由 N 个整数组成的数组(正数和负数)，找到其总和大于或等于 K的连续个子数组的数量(也，正或负)

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)

我设法解决了一个幼稚的O(N ² )解决方案，有可能变得更好吗?

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

推荐答案

是的，可以在O(n log n)时间完成.

Yes, it is possible to do it in O(n log n) time.

1. 让我们看一下前缀总和. (L, R]子数组的总和为prefixSum[R] - prefixSum[L].

这意味着我们可以计算L < R和prefixSum[R] - prefixSum[L] >= K表示prefixSum[L] <= prefixSum[R] - K的L和R的数量.

It means that we can count the number of such L and R that L < R and prefixSum[R] - prefixSum[L] >= K, which means prefixSum[L] <= prefixSum[R] - K.

让我们从左到右遍历前缀和数组，并维护一个可以有效执行以下操作的数据结构:

Let's iterate over the array of prefix sums from left to right and maintain a data structure that can do the following operations efficiently :

• 添加新元素.
• 查找小于或等于给定数目的元素数.

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

We can use a balanced binary search tree for this purpose.

这是此解决方案的伪代码:

Here is a pseudo-code of this solution:

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)中完成.

The time complexity is O(n log n) because there are O(n) add and count number of elements operations, and each of them can be done in O(log n).

这篇关于总和大于给定值的子数组数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！