2003 수들의 합2👊

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력1

4 2
1 1 1 1

예제 출력1

3

예제 입력2

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력2

3

코드

✔ 구간의 부분합을 이용하는 문제
투 포인터는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘이다.
조건은 배열의 원소가 자연수여야 한다는 것이다.
start, end라는 두 개의 포인터를 사용해서 구해야하는 값보다 배열의 부분합이 작으면 mid를 한간 이동하여 배열의 크기를 늘리고 반대로 부분합이 크면 mid를 한간 뒤로 이동하여 배열의 크기를 줄인다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
const numberSum = (limitArr, numArr) => {
  const sumArr = [10001];
  let sum = 0;
  let count = 0;
  let mid = 0;

  const numberArr = Number(limitArr[0]);
  const cutlineNum = Number(limitArr[1]);

  for (let i = 0; i < numberArr; i++) {
    sum += Number(numArr[i]);
    sumArr[i] = sum;
  }
  // unshift를 통해 [0,1,2,3,4...] 배열로 만든다
  sumArr.unshift(0);

  for (let i = 0; i <= numberArr; i++) {
    // start에 포인터 한개, end에 포인터 한개 만든다.
    start = i;
    end = numberArr;

    // 중간지점 mid보다 cutlineNum이 작다면 start를 한칸 앞으로,
    // cutlineNum이 크다면 end를 한칸 뒤로
    while (start <= end) {
      mid = parseInt((start + end) / 2);
      if (cutlineNum > sumArr[mid] - sumArr[i]) {
        start = mid + 1;
      } else if (cutlineNum < sumArr[mid] - sumArr[i]) {
        end = mid - 1;
      } else {
        count++;
        break;
      }
    }
  }
  console.log(count);
};

const inputArr = [];
rl.on("line", (userInput) => {
  inputArr.push(userInput);
}).on("close", () => {
  const limitArr = inputArr[0].split(" ");
  const numArr = inputArr[1].split(" ");
  numberSum(limitArr, numArr);
});