투 포인터(Two Pointer) 알고리즘

1. 개요

1. '부분 연속 수열' 관련된 알고리즘
2. 리스트에 순차적으로 접근해야 할 때 2 개의 점의 위치를 기록하면서 처리하는 알고리즘
3. 시간 복잡도 = O(N)

2. 투 포인터 대표 예제

출처 : https://butter-shower.tistory.com/226

 위의 수열에서 연속 부분 수열의 합이 5가 되는 부분 수열을 구하시오. 

 

3. 알고리즘 동작 원리

출처 : https://butter-shower.tistory.com/226

 

4. 소스 코드 (C++)

#include <iostream>
using namespace std;
 
int main(){
    int N, M, arr[10000];
    cin >> N >> M;
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }
        
    int answer = 0, sum = 0, s = 0, e = 0;
    while(s<N){
        if(sum >= M){ 
            sum -= arr[s];
            s++;
        }else{
            sum += arr[e];
            e++;
        } 
        if(sum == M) answer++;
    }
    
    cout << answer;
}