투 포인터 (Two Pointers)

개념

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

특징

• 시작점과 끝점 2개의 점으로 접근할 데이터의 범위 표현 가능

활용

특정한 합을 가지는 부분 연속 수열 찾기

• N개의 자연수로 구성된 수열에서 합이 M인 부분 연속 수열 개수 구하기
• 수행 시간 제한 : O(N)

문제 해결 아이디어

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 함
2. 현재 부분합이 M과 같다면, 카운트
3. 현재 부분합이 M보다 작다면, end + 1
4. 현재 부분합이 M보다 크거나 같다면, start + 1
5. 모든 경우를 확인할 때까지 2~4번 과정 반복

소스 코드 (Python)

n = #데이터의 개수
m = #찾고자 하는 부분합
data = #전체 수열

count = 0
interval_sum = 0
end = 0

#start를 차례대로 증가시키며 반복
for start in range(n):
	#end를 가능한만큼 이동
    while interval_sum < m and end < n:
    	interval_sum += data[end]
        end += 1
    #부분합이 m일 때 카운트 증가
    if interval_sum == m:
    	count += 1
    interval_sum -= data[start]

성능 분석

• 시간 복잡도 : $O(N)$

---

Reference