Two Pointer_연속 부분수열

✅ n개로 이루어진 수열이 주어질 때, 연속부분수열의 합이 m이 되는 경우가 몇 번 있는지 구하세요

class Main {

    public int solution(int n, int m, int[] intArr){
    int answer= 0;
    int sum=0;
    int lt= 0;
    int rt=lt;
    while(lt<n && rt<n){
            sum += intArr[rt];
            if(sum<m){
                rt++;
            }else if(sum>m){
                lt++;
                rt=lt;
                sum=0;
            }else if(sum==m){
                answer++;
                lt++;
                rt=lt;
                sum=0;
            }

        }

    return answer;
}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] intArr = new int[n];
        for(int i=0; i<n; i++){
            intArr[i] = sc.nextInt();
        }
        System.out.print(T.solution(n, m, intArr));
    }
}

//⭐️input:
// 8 6
// 1 2 1 3 1 1 1 2
//⭐️output:
//3

1. 두 포인터가 있다. lt와 rt. rt는 lt에서부터 시작한다.
   
2. sum 은 lt에서부터 rt까지의 합을 구한다.
   
3. sum이 우리가 구하고자 하는 수 m보다 작으면 rt를 한 개 늘려서 하나의 값을 더 더하고
   
4. sum이 우리가 구하고자 하는 수 m보다 크면 이번 lt에서 m을 구하는 건 글렀으므로 lt를 하나 늘리고 rt와 sum을 초기화한다.
   
5. sum이 우리가 구하고자 하는 수 m과 같으면 정답에 추가하고, lt를 하나 늘리고 rt와 sum을 초기화한다.
   

🔵 ThingsILearned

✔️ Two Pointer 알고리즘이더라도 반드시 오름차순으로 정렬해야 하는 것은 아니다.

✔️ 하나의 배열에서도 Two Pointer 알고리즘을 쓸 수 있다.

✔️ 물론 이 문제는 이중 for문으로도 풀 수 있겠지만, 시간 복잡도가 O의 n제곱일 것이다.