Эффективное нахождение среднего арифметического подмассивов в массиве ⇐ JAVA

[Anonymous]

Я пытаюсь найти несколько способов вычисления среднего арифметического подмассива массива.
Все сводится к этому; учитывая массив 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) работает для небольшого набора данных но это не эффективно. О(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 = X;

if (X == 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;
}


Подробнее здесь: https://stackoverflow.com/questions/630 ... n-an-array