Количество подмассивов размера K со средним значением не менее M

Дан массив arr[] , состоящий из N целых чисел и двух положительных целых чисел K и M , задача состоит в том, чтобы найти количество подмассивов размера K , среднее значение которых не меньше M.

Примеры:

Input: arr[] = {2, 3, 3, 4, 4, 4, 5, 6, 6}, K = 3, M = 4
Output: 4
Explanation:
Below are the subarrays of size K(= 3) whose average is at least M(= 4) as:

1. arr[3, 5]: The average is 4 which is at least M(= 4).
2. arr[4, 6]: The average is 4.33 which is at least M(= 4).
3. arr[5, 7]: The average is 5 which is at least M(= 4).
4. arr[6, 8]: The average is 5.66 which is at least M(= 4).

Therefore, the count of the subarray is given by 4.

Input: arr[] = {3, 6, 3, 2, 1, 3, 9] K = 2, M = 4
Output: 3

Подход: Данная проблема может быть решена с помощью метода двух указателей и скользящего окна. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте переменную, скажем, count как 0 , которая хранит количество всех возможных подмассивов.
• Инициализируйте переменную, скажем, sum как 0 , которая хранит сумму элементов подмассива размера K .
• Найдите сумму первых K элементов массива и сохраните ее в переменной sum . Если значение sum не меньше M*K , то увеличьте значение count на 1 .
• Пройдите по заданному массиву arr[] в диапазоне [K, N – 1], используя переменную i , и выполните следующие шаги:
  • Добавьте значение arr[i] к переменной sum и вычтите значение arr[i – K] из суммы .
  • Если значение sum не меньше M*K , то увеличьте значение count на 1 .
• После выполнения вышеуказанных шагов выведите значение count как результирующее количество подмассивов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)