[Algorithm] 투 포인터

• 리스트에 순차적으로 접근하여 두 개의 위치를 기록하며 처리
• 부분 연속 수열 문제에 사용
• 시간 복잡도 $O(N)$으로 처리 가능

과정

• 설명 다음과 같은 배열에서 합이 M = 5인 부분 수열 개수 찾기 S, E 포인터 위치를 배열의 처음에 두고 시작한다. E 포인터를 계속 이동하면서 E가 가리키는 값을 더한다. S 부터 E 까지의 합이 5 이상이 되면 E는 이동을 멈춘다. 이때 합이 5라면 개수를 센다. S를 한 칸 움직이고 S가 가리키던 값을 뺀다.
  

구현

    int end = 0;
    int sum = 0; // 부분 합
    int cnt = 0; // 개수

	// i 가 start
    for (int i = 0; i < n; i++) {
        while (end < n && sum < m) {
            sum += arr[end];
            end++;
        }

        if (sum == m) {
            cnt++;
        }

        sum -= arr[i];
    }