[Java] 연속부분 수열

문제

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

풀이

연속된 수열을 구하면 이중 for문으로 구하면 쉽지만 시간복잡도가 o(n^2)이므로 좋지 않다.
따라서 포인터를 사용해서 구현해야 한다.
lt와 rt 두개의 포인터를 두고 둘 다 0으로 초기화 시켜준다.
그 다음에 rt가 증가하면서 sum 이라는 변수에 rt를 더해주고 sum이 m과 같은지를 확인한다.
만약 sum이 m보다 커지는 경우에는 lt를 증가시키면서 lt값만큼 sum에서 빼줘야 한다.
그래야 m과 sum이 같은지를 확인할 수 있다.
sum이 m보다 작아지는 순간까지 while문을 돌리고 lt를 증가시면서 sum에서 빼주면서 m과 같아지는 순간 카운팅을 한다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Main {

    public int solution(int n, int m, int[] a) {

        int answer = 0, sum = 0, lt = 0;
        for (int rt = 0; rt < n; rt++) {
            sum += a[rt];

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

            while (sum >= m) {
                sum -= a[lt++];
                if (sum == m) {
                    answer++;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Main solution = new Main();
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        System.out.println(solution.solution(n, m, a));

        /*int m = scanner.nextInt();
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = scanner.nextInt();
        }*/

        /*for (int x : solution.solution(n, m, a, b)) {
            System.out.print(x + " ");
        }*/
    }
}