[알고리즘-JS] 투 포인터 - 연속 부분 수열 합 구하기

문제

N개의 수열과 자연수 M이 입력됩니다. 연속된 부분 수열의 합이 M이 되는 경우가 몇 번 있는지 출력하는 프로그램을 작성하시오.

 

 

입력 예제

8 4

1 3 1 1 2 2 1 2

 

 

출력 예제

4

 

 

풀이

투 포인터를 이용해 탐색한다.

 

function solution(n, m, a) {
  let answer = lt = rt = sum = 0;
  
  for (let rt = 0; rt < n; rt++) {
    sum+= a[rt];
    if (sum === m) answer++;
    
    while(sum >= m) {
      sum -= a[lt++]; // a의 lt 값을 뺀 다음 lt++
      if (sum === m) answer++;
    }
  }
  
  
  return answer;
}