투 포인터 (Two Pointers)

투포인터란?

• 두 개의 포인터를 이용해 한 번의 순회(또는 제한된 순회)로 효율적인 탐색을 수행하는 방법이다.
• 주로 정렬된 배열, 부분합 문제, 중복 제거, 슬라이딩 윈도우, 두 배열 비교 등에 자주 쓰인다.
• 시간 복잡도: O(N)

---

동작 방식

1. 두 개의 포인터 start와 end를 초기 위치에 둔다.
2. 조건에 따라 두 포인터 중 하나 또는 둘 다 이동시킨다.
3. 각 상태에서 필요한 연산(합계 계산, 조건 검사 등)을 수행한다.

---

언제 사용하는가?

• 정렬된 배열에서 합이 특정 값이 되는 쌍을 찾을 때
• 슬라이딩 윈도우 방식으로 길이 제한 조건 하에 계산할 때
• 연속된 구간, 최소 길이, 최대 개수 등의 조건을 만족해야 할 때

---

예제

부분 합이 target 인 경우의 수

 

arr[start] ~ arr[end] 까지의 합을 sum이라 했을때,

• sum == target 인 경우 :  count++;     end++;     sum += arr[end];
• sum > target 인 경우 :  sum -= arr[start];   start++; 
• sum < target 인 경우 :  sum += arr[end];    end++;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int target = 6;

        int start = 0, end = 0, sum = 0, count = 0;

        while (end < arr.length) {
            if (sum == target) {
                count++;
                sum += arr[end++];
            } else if (sum > target) {
                sum -= arr[start++];
            } else {
                sum += arr[end++];
            }
        }

        System.out.println("부분합이 " + target + "인 경우의 수: " + count);
    }
}

 

동작 과정