[Java] 3-4 연속 부분수열

문제

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가지입니다.
입력
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다.
예시 입력

8 6
1 2 1 3 1 1 1 2

예시 출력

3

출처
인프런 - 자바-알고리즘-문제풀이-코테대비

내 풀이

private static int countSubsequence(int num, int m, int[] sequence) {
    int count = 0;

    for (int i = 0; i < num; i++) { // sequence[i]는 부분수열의 첫 숫자
        int sum = 0;
        for (int j = i; j < num; j++) { // i 부터 값을 누적
            sum += sequence[j];
            if (sum > m) { // 목표값을 넘으면 더이상 계산해볼 필요없이 다음 i로
                break;
            } else if (sum == m) { // 목표값이 되면 count올리고 다음 i로
                count++;
                break;
            }
        }
    }
    return count;
}

다른 풀이

/* 강의 풀이 */
public static int solution(int n, int m, int[] arr) {
    int answer = 0, sum = 0, lt = 0;

    for (int rt = 0; rt < n; rt++) {
        sum += arr[rt];
        if (sum == m) answer++;
        while (sum >= m) { // 목표값을 넘으면
            sum -= arr[lt++]; // 목표값보다 작아질 때 까지 왼쪽값을 뺀다
            if (sum == m) answer++;
        }
    }
    return answer;
}

for 반복마다 누적값을 초기화 하지 않기 때문에 내풀이보다 비교횟수가 적다