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

문제

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=8, M=6 
1 2 1 3 1 1 1 2

강사님의 풀이

function solution(m, arr){
    let answer = 0;
    let sum = 0;
    let left = 0;
    //left, right 두개의 포인터로 시작, right는 for문 안에서 증감된다.
    
    for(let right = 0; right<arr.length; right++){
        sum+=arr[right]; //sum에 arr[right]값을 누적한다
        if(sum===m)answer++; //누적된 sum 값이 m과 일치하는지 확인
        
        while(sum>=m){ //sum이 m보다 크거나 같으면, 작아질 때 까지 arr[left]값을 뺀다.
            sum-=arr[left++]; //sum에 arr[left]뺀 값을 누적시키고, ++ 후위 연산한다.
            if(sum===m) answer++ //sum이 m 과 같은지 확인
        }
    }

    return answer;
}

let a=[1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));

• left와 right 두 개의 포인터가 돌며, right 값을 sum에 누적시킨다.
• 만약 누적시킨 값이 m보다 크거나 같다면, 증감되지 않은 left값을 빼면서 증감시킨다. 
• 누적된 sum 값이 m보다 작다면 while문을 빠져나와 다시 right 값을 증감시키며 sum을 누적시킨다.
• 두 가지 경우 모두 sum이 m과 같은지 확인해 같다면 answer를 누적시킨다.

나의 풀이

function solution(m, arr){
    let answer=0;
    let p1 = 0;
    let p2 = 0;
    let sum = 0;
    while(p2<arr.length){ //p2포인터가 length 범위를 빠져나가면 반복이 끝난것으로 간주
        if(sum<m) sum+=arr[p2++]; //sum이 m보다 작은 경우 sum에 arr[p2]를 누적시키고 ++
        if(sum>m) sum-=arr[p1++] //sum이 m보다 큰 경우 sum에서 arr[p1]을 빼고 ++
        if(sum===m){ //sum이 m과 같다면 answer누적
            answer++;
            sum-=arr[p1++]; //left값이 움직여 sum이 작아질 수 있도록 arr[p1]을 빼고 ++
        }

    }

    return answer;
}

let a=[1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));