투 포인터

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 2개의 점 위치를 기록하면서 처리하는 알고리즘을 의미한다. 즉, 시작점과 끝점의 2개의 변수를 이용해 리스트 상의 위치를 기록하여 문제를 해결하는 방식이다. 예시로 특정한 합을 가지는 부분 연속 수열 찾기 문제를 해결해보자. 1 2 3 2 5 의 원소를 갖는 리스트에서 부분 연속 수열의 합계를 5라고 할 때 알고리즘은 다음과 같은 순서로 동작한다.

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

- 이때 부분합이 5이기 때문에 count를 해주고 위 과정을 반복한다.

투 포인터 소스코드

n = 5 #데이터의 개수
m = 5 #찾고하자 하는 부분합
data = [1, 2, 3, 2, 5]

count = 0
interval_sum = 0
end = 0

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]

print(count) #3