Algorithm:투포인터(Two Pointer)

투 포인터 알고리즘

1차원 배열에서 각자 다른 원소를 가진 두개의 포인터를 옮기면서 정답을 얻는 방법

방식

두 개의 포인터 (start,end)를 각각 0으로 셋팅하여 이동한다.

ex) 
10 5
1 2 3 4 2 5 3 1 1 2 에서 5인 합 갯수 세기

left: 빨간색 ,right: 파란색 으로 두고 right를 점차 들려 나간다.

해당 지점에서 합이 5를 넘었기 때문에 left를 늘려준다.

마찬가지로 합이 5이기에 카운트 해주고 left를 늘려준다.

해당 지점에서 합이 5를 넘었기 때문에 left를 늘려준다.

마찬가지로 합이 5이기에 카운트 해주고 left를 늘려준다.

이렇게 증가하다가 right가 끝을 가르키게 되어 더 이상 진행 할 수 없기에 종료한다.

코드

#include <cstdio>
    using namespace std;

int main()
{
    int n = 10; //n: 배열
    int m = 5;  //m : 합
    int cnt = 0;
    int s = 0;
    int arr[] = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2};
    int left = 0, right = 0;
    while (1)
    {
        if (s >= m)
            s -= arr[left++];
        else if (right == n)
            break;
        else
            s += arr[right++];
        if (s == m)
            cnt++;
    }
    cout << cnt << '\n';
}

시간 복잡도

포인터의 증가는 각 n까지만 가능하기 때문에 배열 끝에 도착하면 종료된다.
즉, 시간복잡도는 O(n)이다.

슬라이딩 윈도우(sliding window)

배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘이다.
투 포인터와 차이점은 어느 순간에도 그 구간의 넓이가 동일하다.

ex) 
10 5
1 2 3 4 2 5 3 1 1 2 에서 구간의 넓이가  [2]일 때, 최대 합을 구하여라

시간 복잡도

마찬가지로 시간복잡도는 O(n)이다.

출처
https://m.blog.naver.com/kks227/220795165570
https://www.youtube.com/watch?v=uH9VJRIpIDY