투 포인터

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 리스트 접근 => 시작점과 끝점 2개의 점으로 범위 표현 가능

예시 문제

• 특정한 합을 가지는 부분 연속 수열 찾기
  -> 합이 M인 부분 연속 수열의 개수
• O(N) 시간 제한

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

cnt = 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

    if interval_sum == m:
        cnt += 1
    # 연속된 수열 합에서 앞에꺼 빼버림
    # 뒤에꺼는 남아있는 거임
    interval_sum -= data[start]

print(cnt)

1. 특정 조건을 만족하는 연속 부분 수열을 찾는다.
   s = 0, e = 0 출발
   반복조건: e < n
   같이 뒤로 간다.

2. 특정 조건을 만족하는 두 개의 수를 찾는다.
   s = 0, e = n - 1 출발
   반복조건: s < e
   서로에게 다가간다.