[투포인터 알고리즘] 연속 부분수열1

N개의 수로 이루어진 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.

만약 N=8, M=6이고 12131112 수열이라면
합이 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을 넘지 않는 자연수

function solution(m, arr) {
    let result = 0;

    let a = sum = 0;

    // 배열의 길이만큼 for문을 돌면서 i와 a를 증가해가며 m과 같은 sum을 구함
    for(let i=0; i<arr.length; i++) {
        sum += arr[i];
        if(sum===m) result++;
        while(sum>=m) {
            sum -= arr[a++];
            if(sum===m) result++;
        }
    }

    return result;
}
let arr5 = [1,2,1,3,1,1,1,2];
console.log(solution(6,arr5));  // 3

1. sum에 0번째 배열의 요소 1을 누적 sum = 1
2. sum이 M인 6보다 작기 때문에 while 문을 들어가지 않고 i++
   => sum이 6보다 크거나 같을 때 까지 arr[i] 누적
3. i가 3일 때, sum은 1+2+1+3 = 7이므로 while문에 들어간다.
4. sum에서 0(a)번째 배열의 요소를 빼주며 m과 같으면 result ++
   => 1+2+1+3 에서 1을 빼주니깐 연속된 2+1+3 합이면서 m과 같으니 result++
5. 그 다음 2+1+3에서 1(a)번째 배열의 요소 2를 빼면 while문의 조건에 부합하지 않으므로 i가 증가하며 sum은 1+3+1 = 5가 되며 다시 2번부터 반복