슬라이딩 윈도우 기법

사용 시기: 중첩 루프의 사용을 줄이고 단일 루프로 교체하는 것을 목표로 합니다. 시간 복잡도를 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;
    }
}

동적 크기 슬라이딩 창: 창 크기는 고정되지 않으며 .
그러나 동적 슬라이딩 윈도우 문제에서는 오른쪽 포인터가 목록/배열의 끝으로 초기화되는 기존의 두 포인터 문제와 달리 오른쪽 포인터가 계속 변경됩니다. 일반적으로 기준을 충족하는 하위 배열을 찾으라는 메시지가 표시됩니다.