时间戳

首页 > 解决方案 > 计算给定数组中子数组的数量，其平均值为 k

algorithm - 计算给定数组中子数组的数量，其平均值为 k

问题描述

给定一个整数数组 a 和一个整数 k，我们想设计一种算法来计算子数组的数量，该子数组的平均值为 k。最幼稚的方法是遍历所有可能的子数组并计算相应的平均值。这种简单方法的时间复杂度是 O(n^2)，其中 $n$ 是 a 的长度。我想知道是否有可能比 O(n^2) 做得更好。

通常对于此类问题，将前缀和与哈希图一起使用，但这种技术似乎不适用于这里。

标签： algorithm

解决方案

考虑一个前缀和数组，称之为a。

你想找到所有这样(i, j)的对(a[j]-a[i])/(j-i) == k。

现在看手：

(a[j]-a[i])/(j-i) == k
a[j]-a[i] == k*(j-i)
a[j]-a[i] == k*j-k*i
a[j]-k*j  == a[i]-k*i

因此，如果k*j从j前缀和数组的第 th 个元素中减去，则剩下的任务是计算相同的对。

推荐阅读