Two Pointer/Sliding Window

1. Two Pointer (투 포인터)

• 기본 개념: 배열이나 문자열을 처리할 때, 두 개의 포인터를 사용하여 양 끝에서 또는 같은 방향으로 이동하면서 문제를 해결합니다.

1-1. 정렬된 배열에서 두 수의 합 구하기 (Two Sum)

• 문제: 정렬된 배열에서 두 수의 합이 주어진 값이 되는 두 수의 인덱스를 구합니다.

int[] twoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;  // 합이 작으면 왼쪽 포인터를 오른쪽으로 이동
        } else {
            right--;  // 합이 크면 오른쪽 포인터를 왼쪽으로 이동
        }
    }

    return new int[]{-1, -1};  // 두 수를 찾지 못한 경우
}

1-2. 회문(팰린드롬) 확인

• 문제: 주어진 문자열이 회문인지 확인합니다.

boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;  // 문자가 아닌 경우 건너뜀
        }
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }

        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;  // 대소문자 무시하고 비교
        }
        left++;
        right--;
    }
    return true;
}

---

2. Sliding Window (슬라이딩 윈도우)

• 기본 개념: 고정된 크기 또는 가변 크기의 창을 배열 또는 문자열 위에 슬라이딩 시키며 문제를 해결합니다.

2-1. 최대 길이의 부분 문자열 찾기 (Sliding Window)

• 문제: 주어진 문자열에서 중복 문자가 없는 가장 긴 부분 문자열의 길이를 구합니다.

int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int maxLength = 0;
    int left = 0;

    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));  // 중복 문자를 제거하며 윈도우 축소
            left++;
        }
        set.add(s.charAt(right));
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

2-2. 고정 크기의 슬라이딩 윈도우에서 최대합 찾기

• 문제: 주어진 배열에서 고정된 크기의 슬라이딩 윈도우 내에서 최대합을 구합니다.

int maxSlidingWindowSum(int[] arr, int k) {
    int windowSum = 0;
    int maxSum = Integer.MIN_VALUE;

    // 첫 번째 윈도우의 합 계산
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // 윈도우를 한 칸씩 오른쪽으로 슬라이드
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];  // 새로 추가되는 값은 더하고, 앞쪽 값은 뺌
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

---

3. Two Pointer와 Sliding Window를 함께 사용하는 문제

3-1. 주어진 합을 가지는 부분 배열 찾기 (Subarray with Given Sum)

• 문제: 비음수가 포함된 배열에서, 주어진 합을 가지는 가장 짧은 부분 배열의 길이를 구합니다.

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

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

        while (sum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left++];
        }
    }

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

3-2. 문자열 내의 아나그램 찾기 (Find All Anagrams in a String)

• 문제: 문자열 s에서 p의 아나그램이 되는 부분 문자열을 모두 찾습니다.

List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s.length() < p.length()) return result;

    int[] pCount = new int[26];
    int[] sCount = new int[26];

    // p와 s의 첫 번째 윈도우 초기화
    for (int i = 0; i < p.length(); i++) {
        pCount[p.charAt(i) - 'a']++;
        sCount[s.charAt(i) - 'a']++;
    }

    if (Arrays.equals(pCount, sCount)) {
        result.add(0);
    }

    // 윈도우 슬라이딩
    for (int i = p.length(); i < s.length(); i++) {
        sCount[s.charAt(i) - 'a']++;
        sCount[s.charAt(i - p.length()) - 'a']--;

        if (Arrays.equals(pCount, sCount)) {
            result.add(i - p.length() + 1);
        }
    }

    return result;
}