子数组和大于给定值的子数组数量

Question

给定一个包含N个整数（正数和负数）的数组，找到所有子数组中连续元素的和大于或等于K(也可以是正数或负数)的总个数。

我已经想出了一个朴素的O(N²)解决方案，有没有更好的方法？

- fyquah95

---

星号是用来干什么的？ - JasonN

子数组必须是连续的吗？ - Imran

@jasonN 哎呀，打错字了。我会修正的。 - fyquah95

@Imran 是的。我会把这个加到问题里。 - fyquah95

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)内完成。

- kraskevich

---

这是一个惊人的解决方案。如果有人有 Python 实现轻松拿到手，请分享。 - void

Answer 2

这里有另一种解决方法，它使用了分治法。时间复杂度为 O(n lg n)。

前两个步骤与上面的帖子一样：

1. 创建前缀和数组，将其称为prefixSum []。 2. 这意味着我们必须计算这样的 L 和 R 的数量，即 L < R 且 prefixSum [R] - prefixSum [L] > = K。

现在，让我们创建另一个数组，将其称为arr []，其中对于 i 从 0 到 N-1，arr [i] = prefixSum [N-1-i]。这意味着我们正在创建一个反转的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/

- Duong Hang