투 포인터: 합이 M인 연속 부분수열 개수

O(N²) 완전탐색부터 확인하기

function countByBruteForce(target, numbers) {
  let count = 0;

  for (let start = 0; start < numbers.length; start++) {
    let sum = 0;

    for (let end = start; end < numbers.length; end++) {
      sum += numbers[end];

      if (sum === target) count++;
      if (sum > target) break; // 양수 배열에서만 가능한 조기 종료
    }
  }

  return count;
}

완전탐색은 모든 인덱스를 시작점으로 잡고 오른쪽 끝을 하나씩 늘립니다. 구현이 직관적이고 작은 입력의 정답을 검증하는 기준 함수로 유용하지만, 최악에는 N개의 시작점마다 N개에 가까운 원소를 확인하므로 O(N²)입니다. N이 100,000이면 제출 풀이로 사용하기 어렵습니다.

처음 합을 0으로 두고 현재 원소부터 더하면 [M]처럼 단일 원소 하나가 답인 경우도 빠뜨리지 않습니다. 합이 M을 넘은 뒤 조기 종료하는 규칙은 뒤에 음수가 없다는 조건에서만 안전합니다.

O(N) 투 포인터 정확합 풀이

function countPositiveSubarraysSum(target, numbers) {
  let count = 0;
  let left = 0;
  let sum = 0;

  for (let right = 0; right < numbers.length; right++) {
    sum += numbers[right];

    while (sum > target) {
      sum -= numbers[left++];
    }

    if (sum === target) count++;
  }

  return count;
}

console.log(countPositiveSubarraysSum(5, [1, 3, 1, 2, 3])); // 2

오른쪽 포인터는 새 원소를 창에 넣습니다. 합이 목표보다 커지면 왼쪽 원소를 하나씩 빼서 다시 M 이하로 만듭니다. 조정이 끝난 시점의 합이 M이면 현재 right에서 끝나는 정답 구간을 하나 찾은 것입니다.

모든 원소가 양수이므로 같은 right에 대해 합이 M인 시작점은 최대 하나입니다. 왼쪽을 더 옮기면 합은 반드시 작아지고, 덜 옮기면 M보다 큰 상태이기 때문입니다. 그래서 sum === target일 때 한 번만 증가시키면 됩니다.

M=5 예제 이동 추적표

이 추적에서 정답은 두 구간뿐입니다. 예시 출력은 2여야 하며, 10은 정확합 문제의 결과가 아닙니다.

왜 정확하고 O(N)인가

정확성

right가 이동할 때 합은 커집니다. 합이 M보다 큰 동안 left를 옮기면 합은 엄격하게 감소합니다. 반복이 끝나면 현재 합은 M 이하이고, 양수 조건 때문에 방금 지나친 어떤 left도 M인 구간이 될 수 없습니다. 현재 합이 M이면 그 구간 하나가 정답이고, M보다 작으면 현재 right에서 끝나는 정답 구간은 없습니다.

시간과 공간

right는 0부터 N-1까지 한 번만 이동합니다. left도 뒤로 가지 않고 최대 N번 이동합니다. 각 원소는 창에 한 번 들어오고 최대 한 번 빠지므로 전체 연산은 N에 비례해 O(N)입니다. 별도 자료구조를 만들지 않으므로 추가 공간은 O(1)입니다.

경계 테스트로 구현 검증하기

const assert = require("node:assert/strict");

const positiveCases = [
  { target: 5, numbers: [1, 3, 1, 2, 3], expected: 2 },
  { target: 6, numbers: [1, 2, 1, 3, 1, 1, 1, 2], expected: 3 },
  { target: 3, numbers: [1, 1, 1, 1], expected: 2 },
  { target: 10, numbers: [1, 2, 3], expected: 0 },
  { target: 5, numbers: [5], expected: 1 },
];

for (const testCase of positiveCases) {
  assert.equal(
    countPositiveSubarraysSum(testCase.target, testCase.numbers),
    testCase.expected,
  );
}

검증일은 2026년 7월 19일이며 Node.js v24.15.0에서 위 양수 케이스 5개를 실행했습니다. 완전탐색 함수의 결과와도 모두 대조했습니다.

0·음수가 있으면 누적합 빈도 Map

0이나 음수가 들어오면 창을 늘렸을 때 합이 항상 커지지 않습니다. 또한 0 때문에 같은 right에서 합이 M인 시작점이 여러 개일 수도 있습니다. 이때 투 포인터 한 번 카운트 방식은 정답을 놓칠 수 있으므로 누적합의 등장 횟수를 저장합니다.

function countSubarraysSum(target, numbers) {
  let count = 0;
  let prefix = 0;
  const frequency = new Map([[0, 1]]);

  for (const value of numbers) {
    prefix += value;
    count += frequency.get(prefix - target) ?? 0;
    frequency.set(prefix, (frequency.get(prefix) ?? 0) + 1);
  }

  return count;
}

console.log(countSubarraysSum(1, [1, -1, 1])); // 3
console.log(countSubarraysSum(0, [0, 0]));     // 3

현재 누적합이 prefix라면 이전 누적합이 prefix – target인 위치마다 그 사이 구간의 합이 target입니다. 같은 누적합이 여러 번 나올 수 있으므로 존재 여부가 아니라 빈도를 더합니다. 시작점이 0인 구간도 세기 위해 Map을 [[0, 1]]로 초기화합니다.

이 방법은 0과 음수를 포함해도 평균 O(N)에 동작하며, 서로 다른 누적합을 저장하므로 공간은 O(N)입니다. JavaScript Map API는 MDN Map 문서에서 확인할 수 있습니다.

const generalCases = [
  { target: 1, numbers: [1, -1, 1], expected: 3 },
  { target: 0, numbers: [0, 0], expected: 3 },
  { target: 3, numbers: [1, 2, 3, -3, 3], expected: 5 },
];

for (const testCase of generalCases) {
  assert.equal(
    countSubarraysSum(testCase.target, testCase.numbers),
    testCase.expected,
  );
}

합이 정확히 M과 M 이하인 문제는 다르다

양수 배열에서 합이 M 이하인 모든 구간을 세는 문제는 합을 M 이하로 줄인 뒤, 현재 right에서 끝나는 가능한 시작점 수인 right - left + 1을 누적할 수 있습니다. 그러나 이 수에는 합이 M보다 작은 구간도 들어 있습니다.

따라서 합이 정확히 M인 문제에는 그 개수 공식을 사용하지 않습니다. 이 글의 양수 풀이처럼 sum === target인 창만 한 번 세거나, 0·음수까지 허용되면 누적합 Map을 사용해야 합니다.