언제 쓰나
- 정렬된 배열에서 “합이 K가 되는 쌍을 찾아라”
- 연속 부분 배열 중 “합이 K인/이상인 구간”
- 이중 반복문
O(n²)이 떠올랐는데N이 10만을 넘을 때 — 투포인터가O(n)으로 줄여준다
전제는 단조성이다. 포인터를 한쪽으로 움직였을 때 값(합)이 한 방향으로만 변해야 버린 후보를 다시 볼 필요가 없다. 음수가 섞인 배열의 구간 합은 단조성이 깨져 투포인터를 못 쓴다.
핵심 아이디어
두 포인터가 각자 앞으로만 전진한다. 합이 크면 왼쪽을 좁히고, 작으면 오른쪽을 넓힌다.
A = [1, 2, 3, 4, 2, 5] 목표 M = 5
[1 2] 3 4 2 5 sum=3 < 5 → end를 넓힌다
[1 2 3] 4 2 5 sum=6 > 5 → start를 좁힌다
1 [2 3] 4 2 5 sum=5 = 5 → count++, 계속
1 2 [3 4] 2 5 sum=7 > 5 → ...
start와 end가 각각 최대 n번만 움직인다 → O(n)포인터는 인덱스이고, 합에 더하거나 빼는 것은 그 인덱스가 가리키는 원소 값이다. 인덱스 자체를 더하면 안 된다.
코드 템플릿
“합이 M인 연속 구간의 개수” — 구간형 기본 꼴.
def count_subarrays(arr, m):
count, total = 0, 0
start = 0
for end in range(len(arr)):
total += arr[end] # 구간을 오른쪽으로 확장
while total > m: # 넘치면 왼쪽을 좁힌다
total -= arr[start]
start += 1
if total == m:
count += 1
return count정렬된 배열에서 “합이 K인 쌍” — 양끝 수렴형.
def two_sum_sorted(arr, k):
lo, hi = 0, len(arr) - 1
while lo < hi:
s = arr[lo] + arr[hi]
if s == k:
return (lo, hi)
if s < k:
lo += 1 # 합을 키우려면 왼쪽 전진
else:
hi -= 1 # 줄이려면 오른쪽 후퇴
return None풀이 과정 따라가기
정렬된 배열 [1, 3, 5, 7, 9]에서 합이 12인 쌍을 양끝 수렴으로 찾는 과정이다.
구간형 — [1, 2, 3, 4, 2, 5]에서 합이 5인 연속 구간 세기.
함정
- 인덱스와 값 혼동.
total -= start가 아니라total -= arr[start]다. 이 실수는 예제 몇 개는 통과하기도 해서 더 위험하다. - 음수 원소. 구간형 투포인터는 “확장하면 늘고 축소하면 준다”가 전제다. 음수가 있으면 누적 합 + 해시로 접근을 바꾼다.
- 양끝 수렴형은 정렬 먼저. 정렬 비용
O(n log n)을 포함해도O(n²)완전 탐색보다 훨씬 싸다. - while 조건의 등호.
lo < hi인지lo <= hi인지는 같은 원소를 두 번 쓸 수 있는지에 달렸다. 문제 조건을 먼저 확인한다.