<3.4> 연속 부분수열

문제
: 수열의 개수 N과 임계값 M 그리고 N개의 자연수로 이루어진 수열이 입력으로 주어지면 , 주어진 수열의 element들의 합이 임계값 M이 되는 경우의 수를 구하시오.
EX) N=8 , M=6이고 수열이 {1, 2, 1, 3, 1, 1, 1, 2} 라면
주어진 수열의 부분 수열 {1, 3, 1, 1} , {3, 1, 1, 1} , {1, 1, 1, 2} 에 대해서 부분합이 6이 되므로 , 결과값은 3이 된다.

이 문제의 요구사항은 문제에 주어진 그대로 부분 수열의 합이 임계값이 되는 경우의 개수를 count하는 것이다.

일단 풀이 코드는 다음과 같다

import java.util.Scanner;

public class Main {


    public static int solution(int[] arr, int N, int M){
        int sum = 0;
        int cnt = 0;
        int lt=0, rt=1;

        sum += arr[lt];
        while(lt<N){
            if(sum < M){
                if(rt<N){
                    sum += arr[rt++];
                } else{
                    sum -= arr[lt];
                    lt++;
                }
            }
            else if(sum == M){
                cnt++;
                sum -= arr[lt];
                lt++;
            }
            else{
                sum -= arr[lt];
                lt++;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {

        //0. Scanner 준비
        Scanner sc = new Scanner(System.in);

        //1. 입력
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        //2. solution() 호출
        int result = solution(arr, N, M);

        //3. 결과 출력
        System.out.println(result);
    }
}