总和大于给定值的子数组个数

Question

给定一个包含N个整数（正负）的数组，找出连续个子数组的总和大于或等于的个数到 K（也，正或负）

我已经想出了一个天真的 O(N²) 解决方案，是否有可能变得更好？

Answer 1

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

我们来看看前缀和。 (L, R] 子数组的和是 prefixSum[R] - prefixSum[L].
就是说我们可以统计出这样的L和R的个数，即L < R和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).

中完成

Answer 2

这是另一种解决方案，它使用分而治之的方法。时间复杂度为 O(n lg n).

前两步同上post:

创建前缀和，我们称它们为prefixSum[]。
就是说我们要统计这样的L和R的个数，L < R和prefixSum[R] - prefixSum[L] >= K。
现在，让我们创建另一个数组，我们称之为 arr[]，其中 arr[i] = prefixSum[N - 1 - i] for i from 0 to N - 1 .这意味着我们正在创建一个反向的 prefixSum[] 数组。

现在我们要统计i和j和i < j和arr[i] - arr[j] >= K的数量。为此，我们将使用合并排序（使用 D & C 方法）：

假设我们有：

MergeSort(arr, left, right):
    mid = (left + right) / 2
    MergeSort(arr, left, mid)
    MergeSort(arr, mid + 1, right)
    Merge(arr, left, mid, right)

在Merge函数中，我们必须添加：

i = left - mid       # Index for the left array
j = mid + 1 - right  # Index for the right array

if (arr[i] >= arr[j]):
    if (arr[i] >= arr[j] + K):
        count += (mid - i + 1)
        # Because arr[] from i to mid are all
        # greater or equal to arr[i] so if arr[i] >= arr[j] + K
        # then arr[] from i to mid are all >= arr[j] + K.
else:
    if (arr[i] >= arr[j] + K): # K can be negative.
        count += mid - i + 1;

这个想法与计算数组中的反转是一样的
https://www.cdn.geeksforgeeks.org/counting-inversions/

总和大于给定值的子数组个数

Number of Subarray whose sum greater than given value

algorithm

data-structures