[알고리즘] Range: Sliding Window

1. Sliding Window

• 선형 자료구조에서 특정 크기의 연속된 구간을 찾는 알고리즘 입니다.
• 일정한 크기의 구간을 움직여 찾습니다.

 

동작 원리

1. 윈도우 설정: 초기 윈도우 구간을 설정함
2. 윈도우 이동: 한 번에 한 요소씩 이동시킴 (왼쪽 끝 제거 + 오른쪽으로 이동)
3. 조건 확인: 각 윈도우가 특정 조건을 만족하는지 확인

 

최대 구간 합) 고정 크기 

public int maxSumK(int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum+=arr[i];
    int ans = sum;
    
    for (int j = k; j < arr.length; j++) {
    	sum += arr[j];
        sum -= arr[j-k];
        ans = Math.max(ans, sum);
    }
    
    return ans;
}

 

최대 구간 합) 가변 크기 + 부분 합 제한

public int longestLenSumLt(int S) {
    int n = arr.length;
    int l = 0, sum = 0, ans = 0;

    for (int r = 0; r < n; r++) {
        sum += arr[r];

        while (sum > S && l <= r) sum -= arr[l++];

        ans = Math.max(ans, r-l+1);
    }

    return ans;
}

 

 

장점

• 성능 (O(n))
• in-place

 

2. 문제

subarray

• Minimum Size Subarray Sum (문제) (해설)
• Longest Substring Without Repeating Characters (문제) (해설)