투 포인터 & 슬라이딩 윈도우

투 포인터(Two Pointer)

두 개의 포인터(인덱스)를 사용해 O(N²) 탐색을 O(N)으로 줄이는 기법입니다.

대표 패턴 1: 합이 K인 쌍 찾기 (정렬된 배열)

// 정렬된 배열에서 합이 target인 쌍
vector<pair<int,int>> twoSum(vector<int>& arr, int target) {
    vector<pair<int,int>> result;
    int left = 0, right = arr.size() - 1;

    while (left < right) {
        int sum = arr[left] + arr[right];
        if      (sum == target) { result.push_back({arr[left++], arr[right--]}); }
        else if (sum < target)  { left++;  }
        else                    { right--; }
    }
    return result;
}

대표 패턴 2: 합이 K 이상인 최소 연속 구간

// 합이 target 이상인 가장 짧은 연속 부분 배열 길이
int minSubarrayLen(vector<int>& nums, int target) {
    int left = 0, sum = 0, minLen = INT_MAX;

    for (int right = 0; right < nums.size(); right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

슬라이딩 윈도우(Sliding Window)

고정 또는 가변 크기의 윈도우를 한 방향으로 이동시키며 구간 정보를 유지합니다.

고정 크기 윈도우: 크기 K인 최대 합

int maxSumFixedWindow(vector<int>& nums, int k) {
    int windowSum = 0, maxSum;

    // 초기 윈도우
    for (int i = 0; i < k; i++) windowSum += nums[i];
    maxSum = windowSum;

    // 슬라이딩
    for (int i = k; i < nums.size(); i++) {
        windowSum += nums[i] - nums[i - k];  // 추가 - 제거
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

가변 크기 윈도우: 중복 없는 최장 부분 문자열

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> lastPos;
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        if (lastPos.count(c) && lastPos[c] >= left)
            left = lastPos[c] + 1;  // 중복 발생 → 윈도우 수축

        lastPos[c] = right;
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

가변 크기 윈도우: K개 이하의 고유 문자를 포함하는 최장 구간

int longestSubstringKDistinct(string s, int k) {
    unordered_map<char, int> freq;
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.size(); right++) {
        freq[s[right]]++;

        while (freq.size() > k) {
            freq[s[left]]--;
            if (freq[s[left]] == 0) freq.erase(s[left]);
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

슬라이딩 윈도우 최솟값/최댓값 (Deque 활용)

// 크기 K인 슬라이딩 윈도우의 최댓값
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;  // 인덱스 저장, 감소 단조 큐
    vector<int> result;

    for (int i = 0; i < nums.size(); i++) {
        // 윈도우 벗어난 인덱스 제거
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();

        // 현재 값보다 작은 값 제거 (뒤에서)
        while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();

        dq.push_back(i);
        if (i >= k - 1) result.push_back(nums[dq.front()]);
    }
    return result;
}

적용 조건 체크리스트

투 포인터/슬라이딩 윈도우 적용이 가능한 경우:

• ✅ 연속 구간(Subarray/Substring) 문제
• ✅ 단조성: right 확장 시 조건이 단순하게 변화 (합 증가, 집합 추가 등)
• ✅ left ≤ right 순서가 유지되며 포인터가 한 방향으로만 이동
• ❌ 구간 내 순서가 중요하거나 비연속 탐색이 필요한 경우

정리

패턴	자료구조	복잡도	사용 예
두 포인터 합	배열 (정렬)	O(N)	합이 K인 쌍
가변 윈도우	HashMap	O(N)	중복 없는 최장 구간
고정 윈도우	누적합	O(N)	크기 K 최대 합
단조 덱 윈도우	Deque	O(N)	윈도우 최솟값/최댓값