투 포인터 알고리즘 응용 - 특정한 합 가지는 부분 연속 수열 찾기

투 포인터 알고리즘 : 리스트에 순차적으로 접근할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 (시작점과 끝점 설정)

✅ 문제

• n개의 자연수로 구성된 수열이 있다.
• 합이 m인 부분 연속 수열의 개수를 구하여라.
• 수행 제한 시간은 O(N)이다.

ex) 1 2 3 2 5 -> (2, 3), (3, 2), (5) 따라서 출력값 : 3

💻 코드

import java.util.*;

public class TwoPointer
{
    public static int n = 5; // 데이터의 개수 N
    public static int m = 5; // 찾고자 하는 부분합 M
    public static int[] arr = {1, 2, 3, 2, 5}; // 전체 수열

    public static void main(String[] args)
    {
        int cnt = 0, intervalSum = 0, end = 0;
        for (int start = 0; start < n; start++) { // start를 차례대로 증가시키며 반복
            while (intervalSum < m && end < n) // end를 가능한 만큼 이동
            {
                intervalSum += arr[end];
                end += 1;
            }
            if (intervalSum == m)
            {
                cnt += 1;
            }
            intervalSum -= arr[start];
        }

        System.out.println(cnt);
    }
}

📝 정리

투 포인터를 활용하여 알고리즘으로 문제를 해결한 순차
1. 시작점과 끝점이 첫번째 원소의 인덱스(0)를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면, 카운트한다.
3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.