Coding Test(Two Pointer)

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

 

아마 투 포인터를 몰랐다면 완전 탐색을 이용해서 O(N^2)만큼 했을텐데 투 포인터를 이용하면 선형 관계에서 해결 가능

 

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

count = 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
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]

print(count)

 

 

 

https://www.youtube.com/watch?v=ttLRltNDiCo&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=39