슬라이딩 윈도우

한 줄 정의

연속 부분배열·부분문자열에서 오른쪽 끝을 늘리고, 조건이 깨지면 왼쪽 끝을 줄이며 최적·유효 구간을 찾습니다.
본질은 같은 방향 투포인터 + 구간 상태(합, 빈도 맵 등)입니다.

고정 길이 윈도우

길이 k인 구간만 보면 됩니다.

def max_sum_k(arr, k):
    s = sum(arr[:k])
    best = s
    for i in range(k, len(arr)):
        s += arr[i] - arr[i - k]
        best = max(best, s)
    return best

한 칸 밀 때마다 O(1) 갱신 → 전체 O(n).

가변 길이 윈도우

예: “서로 다른 문자가 최대 k개”, “합이 target 이하인 최장 구간”.

function longestAtMostKDistinct(s, k) {
  const freq = new Map();
  let lo = 0, best = 0;
  for (let hi = 0; hi < s.length; hi++) {
    freq.set(s[hi], (freq.get(s[hi]) || 0) + 1);
    while (freq.size > k) {
      const c = s[lo++];
      freq.set(c, freq.get(c) - 1);
      if (freq.get(c) === 0) freq.delete(c);
    }
    best = Math.max(best, hi - lo + 1);
  }
  return best;
}

불변식

루프 진입 시 [lo, hi]가 항상 유효한 구간이 되게 while로 lo를 당깁니다.

언제 쓰나

• “연속”, “부분배열”, “부분문자열”
• 구간에 원소를 더하면 합/종류 수가 단조적으로 변함
• n이 커서 O(n²) 불가

함정

1. lo를 줄일 때 맵·합을 같이 되돌리기
2. 빈 구간·전체 구간 경계
3. 고정 길이와 가변 길이를 혼동
4. 문자 빈도 0인 키를 맵에 남겨 size가 커지는 실수 (JS)

복잡도

각 인덱스가 hi로 한 번, lo로 최대 한 번 이동 → O(n) 시간.
문자종류·해시 공간은 O(Σ) 또는 O(k).

투포인터·해시와의 관계

슬라이딩 = 투포인터 + (자주) 해시 상태.
앞 레슨 두 개를 읽고 오면 이 패턴이 자연스럽게 붙습니다.