Техника раздвижных окон

Когда использовать: Цель — сократить использование вложенных циклов и заменить их одним циклом. Уменьшает временную сложность с O(n^2) до O(n).

Два типа скользящего окна:

Фиксированная длина окна k: длина окна фиксирована, и вас попросят найти что-то в окне. Например, максимальную сумму или максимальное среднее значение каждого окна.
Сначала мы начинаем с получения суммы окна размером k и отслеживаем максимальное значение, затем сдвигаем его, удаляя слева и добавляя справа.

class Solution {
    public double findMaxAverage(int[] nums, int k) {

        double maxAverage = 0;
        int sum = 0;

        for(int i = 0; i < k; i++){
            sum += nums[i];
        }

        maxAverage = sum;

        for(int i = k; i < nums.length; i++){
            sum += nums[i] - nums[i - k];
            maxAverage = Math.max(maxAverage, sum);
        }

        return maxAverage/k;
    }
}

Раздвижное окно динамического размера: Размер окна не фиксирован и также известен как техника двух точек.
Однако в задаче с динамическим скользящим окном правый указатель будет постоянно меняться, в отличие от традиционной задачи с двумя указателями, где правый указатель инициализируется как конец списка/массива. Обычно вас просят найти подмассив, удовлетворяющий заданным критериям.