数组中平均值大于或等于 k 的子数组总数

Question

给定一个大小为 N 的数组 A 和一个整数 k。求平均值大于或等于 k 的不同大小的子数组的总数。

Constraints :
1 <= N <= 10^5
-10^9 <= A[i] <= 10^9
-10^9 <= k <= 10^9

注意：我通过维护一个 prefix Sum 数组并检查所有大小的所有子数组来完成这个问题。但我正在接受 TLE。

我们可以做得更好（优化）吗？

Answer 1

这是一个非常有趣的问题，也是一个非常流行的问题的变体（稍后提到）。

在这里，我们必须找到带有

mean >= k

的子数组的数量。

从数学上来说，

=>

(a[i] + a[i + 1] + ... + a[i + l - 1]) / l >= k

=>

(a[i] + a[i + 1] + ... + a[i + l - 1]) >= k * l

=>

((a[i] - k) + (a[i + 1] - k) + ... + (a[i + l - 1] - k) >= 0

...（等式 1）

现在让我们将原始数组的所有元素减去k。

经过此转换，我们的任务是找到具有

sum >= 0

的子数组的数量（来自等式 1）

我们可以把这个问题分成两部分（我不会写整个逻辑的实现，只是提供如何解决这个问题的逻辑）：

第 1 部分：查找总和为零的子数组的数量

这非常简单，我们只需使用

hashmap

和

prefix sum

即可完成。你之前一定已经解决了。

第 2 部分：查找 sum > k 的子数组数量

这很有趣。为了解决这个子问题，我们首先为转换后的数组构建一个

prefix sum array

。

哪里，

prefix[i] = arr[0] + arr[1] + ... + arr[i]

现在，对于每个索引

i

，我们必须找到子数组

prefix[i]

中小于

prefix[0...(i - 1)]

的元素数量。

现在，您可以注意到，这只是著名问题计算数组中的反转数的变体（您只需修改该代码即可找到右侧大于当前元素的数量）。这个子问题可以用这个逻辑来解决（你可以通过它或者你必须更早解决这个问题）。

最终答案将是我们从第 1 部分和第 2 部分获得的这两个计数的总和。 这就是这个问题背后的全部逻辑。

时间复杂度为 O(n*log(n))

希望有帮助！有疑问可以在评论里提问。