투포인터 알고리즘

• 말 그래도 두개의 점을 이용하는 알고리즘이다.
• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 포함할 수 있다.

예시

• N = 8개의 자연수로 구성된 수열이 있다.
• 합이 M = 5인 부분 연속 수열의 개수를 구하여라.
• 제한은 O(N)이다.

const N = [3, 2, 4, 1, 2, 2, 1, 5];
const M = 5;

let answer = 0;

let sum = 0;
let end = 0;
// start를 고정시켜놓고 start를 차례대로 증가시킨다.
for (let start = 0; start < N.length; start++) {
  // end를 가능한 만큼 이동시킨다.
  while (sum < M && end < N.length) {
    sum += N[end];
    end += 1;
  }
  if (M === sum) answer += 1;
  sum -= N[start];
}

console.log(answer);