[알고리즘] 투 포인터 + 문제풀이

투 포인터

• 리스트에서 순차적으로 처리할 때 두 개의 점(start, end)으로 기록하며 처리하는 알고리즘
• 완전탐색은 O(N^2), 투 포인터는 O(N)

 

코드

n = 5
m = 5
data = [1,2,3,2,5]

cnt = 0
interval_sum = 0
end = 0

for start in range(n):
  while interval_sum < m and end < n: #부분합이 더 작으면 end를 이동
    interval_sum += data[end]
    end+=1
  if interval_sum == m:
    cnt+=1
  interval_sum -= data[start] #부분합이 더 크면 start를 이동

print(cnt)

 

관련 문제

- 백준 2018번 연속된 자연수의 합 구하기 (실버5) O

- 백준 1940번 주몽의 명령 (실버4)