我正在尝试找到计算数组子数组算术平均值的方法。
问题可以归结为:给定数组X和整数S,有多少个连续的X片段的算术平均值等于S?例如,对于 X=[5,3,6,2] 和 S=4,结果为3。[5,3],[6,2]和[5,3,6,2]的平均值都为4。
X可能最多有100,000个元素。每个X值都是{-1,000,000,000,+1,000,000,000}范围内的整数。S也是如此。我们不会四舍五入计算出的算术平均值。
下面是我的Java代码,适用于小数据集但效率不高,O(n^2)。
public static int returnSubsequenceCount(int[] X, int S) {
int counter = 0;
for (int i = 0; i < X.length; i++) {
int[] dpSum = new int[X.length];
dpSum[i] = X[i];
if (X[i] == S) {
counter++;
}
for (int j = i + 1; j < X.length; j++) {
int sum = dpSum[j - 1] + X[j];
dpSum[j] = sum;
if ((double) sum / (j - i + 1) == S) {
counter++;
}
}
}
return counter;
}