1. 概述
本教程将学习如何高效计算数组中满足特定算术平均值的连续子数组数量。
我们从时间复杂度为O(n²)的暴力解法开始，分析其性能瓶颈后，利用前缀和和频率映射将其优化至线性时间复杂度O(n)。
2. 问题定义
给定一个整数数组和一个目标平均值，我们需要统计所有连续子数组中满足算术平均值等于目标值的子数组数量。例如，对于数组[5, 3, 6, 2]和目标平均值4，正确结果是3，因为以下子数组的平均值均为4：
[5, 3]( (5+3)/2 = 4 )[6, 2]( (6+2)/2 = 4 )[5, 3, 6, 2]( (5+3+6+2)/4 = 4 )
问题约束条件： ✅ 数组长度最大100,000 ✅ 元素值范围：[-1,000,000,000, +1,000,000,000] ✅ 目标平均值范围同上
3. 暴力解法
最直观的方案是使用双重循环枚举所有子数组：
static int countSubarraysWithMean(int[] inputArray, int mean) {
int count = 0;
for (int i = 0; i < inputArray.length; i++) {
long sum = 0;
for (int j = i; j < inputArray.length; j++) {
sum += inputArray[j];
if (sum * 1.0 / (j - i + 1) == mean) {
count++;
}
}
}
return count;
}
⚠️ 性能陷阱：虽然实现简单，但时间复杂度为O(n²)。对于100,000个元素的数组，需要执行约50亿次操作，显然不可接受。
4. 线性解法
要优化至O(n)，需要理解两个关键概念：前缀和与频率映射。
4.1. 前缀和与频率映射原理
定义两个数组：
P[i]：前缀和数组，P[i] = X[0] + X[1] + ... + X[i]Q[i]：调整前缀和数组，Q[i] = P[i] - S * i（S为目标平均值）
对于任意子数组[i, j]，若其平均值等于S，则满足：
Q[j] = P[j] - S * j
= (P[j] - P[i-1]) - S * (j - (i-1))
= (子数组[i,j]的和) - (子数组长度 * S)
= Q[i-1]
核心洞察：当Q[j] = Q[i-1]时，子数组[i, j]的平均值恰好为S。因此问题转化为：在调整前缀和数组Q中，统计相同值出现的次数。
4.2. Java实现
static int countSubarraysWithMean(int[] inputArray, int mean) {
int n = inputArray.length;
long[] prefixSums = new long[n+1];
long[] adjustedPrefixes = new long[n+1];
// 计算前缀和与调整前缀和
for (int i = 0; i < n; i++) {
prefixSums[i+1] = prefixSums[i] + inputArray[i];
adjustedPrefixes[i+1] = prefixSums[i+1] - (long) mean * (i+1);
}
// 使用频率映射统计相同值出现次数
Map<Long, Integer> countMap = new HashMap<>();
int total = 0;
for (long adjustedPrefix : adjustedPrefixes) {
total += countMap.getOrDefault(adjustedPrefix, 0);
countMap.put(adjustedPrefix, countMap.getOrDefault(adjustedPrefix, 0) + 1);
}
return total;
}
关键点解析：
- 使用
long类型避免整数溢出 - 调整前缀和计算：
Q[i] = P[i] - S * i - 频率映射统计：遍历时累加已出现相同值的次数
复杂度分析：
- 时间复杂度：O(n)（两次线性遍历）
- 空间复杂度：O(n)（两个长度为n的数组 + 频率映射）
5. 总结
本文解决了计算特定平均值子数组数量的问题：
- 暴力解法O(n²)适用于小规模数据
- 基于前缀和与频率映射的优化解法O(n)可处理大规模数据
- 核心技巧：通过数学变换将平均值问题转化为调整前缀和的相等值查找问题
完整代码实现可在GitHub获取。