[Python] 투 포인터(Two Pointers)

• 특정 조건(보통은 구간 합)을 만족하는 부분연속 수열을 찾을 때 사용

import sys

# 데이터의 개수 N과 구하고자 하는 부분 연속 수열의 합 M
N, M = map(int, sys.stdin.readline().split())

# 수열
seq = list(map(int, sys.stdin.readline().split())

# 인덱스 초기화, 
start = 0
end = 0

# 구간 합 초기화
S = seq[start]

# 누적 합 M을 만족하는 수열의 개수
cnt = 0

# Two Pointers Algorithm
while True:
	
    # 구간합이 S보다 작을 때
	if S < M:
    	
        # 더 이상 마지막 인덱스를 증가시킬 수 없으므로 종료
       	if end == N-1:
        	
            break
            
        # 마지막 인덱스 추가
    	end += 1
        
        # 마지막 인덱스 수 누적
        S += seq[end]
    
    elif S >= M:
    
    	if S == M:
        	
            cnt += 1
        
        # 시작 인덱스 값을 뺀다
        S -= seq[start]
        
        # 시작 인덱스 1 증가
        start += 1

# 만족하는 부분 수열의 합 개수 출력
print(cnt)