연속부분수열

문제

나의 코드

let N = 8;
let M = 6;
let arr = [1,2,1,3,1,1,1,2];
----------------------------------
let p1=0;
let p2=1;
let sum = arr[p1] + arr[p2];
let cnt = 0;
while(p1<N && p2<N){
    if(sum < M){
        sum += arr[p2+1];
        p2++;        
    } 
    else if(sum === M){
        cnt++;
        sum -= arr[p1];
        p1++
        sum += arr[p2+1];
        p2++     
    }
    else{
        sum -= arr[p1];
        p1++;
    } 
}
console.log(cnt);

원리

• 투포인터(p1,p2)를 각각 arr[0],arr[1]에 초기화 한다, sum = arr[0] + arr[1]로 초기화 한다.
• sum < M이면 p2를 오른쪽으로 옮긴다. (sum = arr[p1]~arr[p2]까지의 합)
• sum === M이면 p1,p2모두 오른쪽으로 옮긴다.
• sum > M이면 p1을 오른쪽으로 옮긴다.

다른 풀이

let n = 8;
let m = 6;
let arr = [1,2,1,3,1,1,1,2];
----------------------------------
let answer=0, lt=0, sum=0;
for(let rt=0; rt<arr.length; rt++){
  sum+=arr[rt];
  if(sum===m) answer++;
  while(sum>=m){
    sum-=arr[lt++]; //[lt++]는 sum-=arr[lt]를 한 후 lt++를 해준다는 뜻이다.
    if(sum===m) answer++;       
  }
}
console.log(answer);

원리

• rt는 계속 오른쪽으로 움직인다.
• lt는 sum>=m일때만 움직인다.
  ">="를 한 이유는 sum === m이면 lt도 움직여 줘야 하기 때문이다.