투 포인터와 슬라이딩 윈도우 — 배열 문제를 O(n)으로 바꾸는 기법

// 정렬된 배열에서 합이 target인 두 수의 인덱스 찾기
public static int[] twoSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left < right) {
        int sum = arr[left] + arr[right];

        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;   // 합을 키워야 하므로 왼쪽 포인터를 오른쪽으로
        } else {
            right--;  // 합을 줄여야 하므로 오른쪽 포인터를 왼쪽으로
        }
    }
    return new int[]{-1, -1}; // 없음
}

public static int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxWater = 0;

    while (left < right) {
        int h = Math.min(height[left], height[right]);
        int width = right - left;
        maxWater = Math.max(maxWater, h * width);

        // 더 낮은 쪽을 이동시켜야 높이를 높일 가능성이 있음
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

public static int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0;
    int minLen = Integer.MAX_VALUE;

    for (int right = 0; right < nums.length; right++) {
        sum += nums[right]; // 오른쪽 포인터 확장

        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left]; // 왼쪽 포인터 축소
            left++;
        }
    }

    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastIndex = new HashMap<>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        // 중복 문자가 현재 윈도우 안에 있으면 left를 이동
        if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
            left = lastIndex.get(c) + 1;
        }

        lastIndex.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

// 크기 k인 연속 부분 배열의 최대 합
public static int maxSumSubarray(int[] arr, int k) {
    // 첫 윈도우의 합 계산
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    int maxSum = windowSum;

    // 윈도우를 한 칸씩 밀기
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i];       // 새로 들어오는 원소 추가
        windowSum -= arr[i - k];   // 나가는 원소 제거
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

// 합이 target 이하인 가장 긴 부분 배열 (양수만 있는 경우)
public static int longestSubarrayWithSum(int[] arr, int target) {
    int left = 0, sum = 0, maxLen = 0;

    for (int right = 0; right < arr.length; right++) {
        sum += arr[right];

        while (sum > target) {
            sum -= arr[left];
            left++;
        }

        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

public static int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>(); // 인덱스 저장
    int[] result = new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        // 윈도우 범위를 벗어난 원소 제거
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // 현재 원소보다 작은 원소들은 더 이상 최대값이 될 수 없으므로 제거
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        // 윈도우가 완성된 시점부터 결과 기록
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

// 이런 경우 투 포인터가 안 됩니다:
// 배열 [-1, 2, -3, 4]에서 합이 2인 부분 배열
// → 음수 때문에 합이 감소했다 증가하므로 단조성 X
// → 이 경우 해시맵(prefix sum)을 사용합니다

// 합이 target인 부분 배열 개수 (음수 포함)
public static int subarraySum(int[] nums, int target) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);

    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        count += prefixCount.getOrDefault(sum - target, 0);
        prefixCount.merge(sum, 1, Integer::sum);
    }
    return count;
}

[전송완료 | 전송가능 윈도우 | 아직 전송 불가]
  ←ACK→   ←   rwnd    →

// Redis를 이용한 슬라이딩 윈도우 Rate Limiter 개념
// ZADD rate_limit:{userId} {timestamp} {requestId}
// ZRANGEBYSCORE rate_limit:{userId} {now - windowSize} {now}
// 윈도우 밖의 오래된 요청은 제거