투 포인터 (Two Pointers)

배열에서 두 개의 포인터(인덱스)를 동시에 움직이며 조건을 만족하는 구간이나 쌍을 찾는 알고리즘

• 보통 정렬된 배열에서 사용하는 것이 일반적
• 시간 복잡도를 O(n²) → O(n) 또는 O(n log n) 수준으로 줄이기 위해 사용
• 두 포인터는 일반적으로 같은 방향으로 이동하거나 양쪽 끝에서 안쪽으로 좁혀가며 탐색
• 슬라이딩 윈도우(Sliding Window)와도 유사하지만, 투 포인터는 특정 조건을 만족하는 조합을 찾는 데 중점
• 장점
  • O(n), O(n log n)의 빠른 시간 복잡도
  • 반복문 중첩 없이 배열을 효율적으로 탐색
  • 구간합, 정렬된 배열의 쌍 문제 등에 특히 유용
• 단점
  • 배열이 정렬되어 있어야 사용할 수 있는 경우 많음
  • 조건문 구성이나 종료 조건이 꼼꼼해야 함

적용 조건

• 정렬된 배열에서 두 수의 합을 찾을 때
• 특정 부분 배열이나 구간을 빠르게 찾고자 할 때
• 연속된 수열 / 부분합을 만족하는 구간이 필요할 때
• 두 배열 비교, 교집합 찾기 등에도 활용 가능

진행 과정

1. 배열을 정렬 (필요 시)
2. 시작 포인터 left, 끝 포인터 right를 초기화
3. 반복문을 돌면서 조건 비교
4. 조건에 따라 포인터를 이동시킴
   • 합이 너무 크면 right--
   • 합이 작으면 left++ 등
5. 조건에 맞는 구간이 발견되면 처리

구현 코드 예시

자주 사용되는 ADT

대부분 배열로 만들어진 자료구조를 기반으로 구현됨

자료구조	설명	활용 예
배열	탐색 대상 기본 구조	정렬된 배열의 합, 부분합
정렬된 배열	값 비교 최적화	투포인터 전제 조건
슬라이딩 윈도우 배열	일정 범위의 값 추적	연속된 수열 탐색
문자열 배열	문자열 비교 문제	아나그램, 회문 쌍

예시 1: 정렬된 배열에서 두 수의 합이 target인 쌍 찾기

const twoSum = (nums, target) => {
  nums.sort((a, b) => a - b); // 정렬 필수
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [nums[left], nums[right]];
    else if (sum < target) left++;
    else right--;
  }

  return []; // 조건 만족하는 쌍 없음
};

예시 2: 연속된 부분 수열의 합이 S 이상인 최소 길이

// 슬아이딩 윈도우와 투 포인터가 결합된 형태
const minSubArrayLen = (target, nums) => {
  let left = 0, sum = 0, minLen = Infinity;

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

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

  return minLen === Infinity ? 0 : minLen;
};

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • 정렬 O(n log n)
  • 포인터 탐색 O(n)
  • → 최종 O(n log n) 또는 O(n)
• 공간 복잡도
  • O(1): 포인터만 사용하므로 추가 메모리 없음

대표 문제 유형 및 핵심

문제	키워드	상태 표현식	포인터 이동 / 조건 로직
Two Sum II	정렬된 배열에서 쌍 찾기	left, right	sum < target → left++, sum > target → right--
Minimum Size Subarray Sum	연속된 수열 / 최소 길이	left, right, sum	sum ≥ target → left++, sum < target → right++
3Sum	세 수의 조합	i, left, right	sum === 0 → 정답 저장, 나머진 위와 동일
회문 판단	양끝 비교	start, end	s[start] !== s[end] → false, 점점 좁힘
교집합 / 차집합	두 배열 비교	i, j (두 배열 포인터)	arr1[i] === arr2[j] → 저장, 작으면 해당 포인터 증가