[투포인터] (이론+문제) 특정한 합을 가지는 부분 연속 수열 찾기

📌 투포인터 알고리즘이란?

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

 

📌 어떤 경우 쓰일까?

ex) 특정한 합을 가지는 부분 연속 수열 찾기 (대표적)

 

📌 알고리즘

1️⃣ 시작점(start)과 끝점(end)이 첫번째 원소 인덱스(0)를 가르키도록함

2️⃣  while 현재 부분합이 M보다 작으면 end를 증가시킴 (부분합이 M보다 같거나 크기 전까지)

3️⃣ 부분합이 M이랑 같으면 카운트함

4️⃣ 부분합에서 시작점(start)의 원소를 제거  

5️⃣ 시작점(start) 인덱스를 1증가

2️⃣~5️⃣  반복

 

📌 기본 코드

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

count = 0
end = 0
interval_sum = 0

for start in range(n):
    while interval_sum<m and end<n:
        interval_sum+=sequence[end]
        end+=1
    if interval_sum==m:
        count+=1
    interval_sum-=sequence[start]

print(count)

 

📌  (프로그래머스_178870) 연속된 부분 수열의 합

✅ 구간합 문제인 줄 알았는데 대표적인 투포인터 문제였음

from heapq import heappop,heappush

def solution(sequence, k):
    end = 0
    interval_sum = 0
    n = len(sequence)
    hq = []
    for start in range(n):
        while interval_sum<k and end<n:
            interval_sum+=sequence[end]
            end+=1
        if interval_sum==k:
            heappush(hq,(end-start+1,[start,end-1]))
        interval_sum-=sequence[start]
    answer = heappop(hq)[1]
    return answer