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

• 문제와 양수 조건
• O(N²) 완전탐색
• O(N) 투 포인터
• 이동 추적표
• 정확성·복잡도 증명
• 경계 테스트
• 0·음수 입력: 누적합 Map
• 정확히 M과 M 이하의 차이
• FAQ

문제와 양수 조건

N개의 자연수로 이루어진 배열에서 합이 정확히 M인 연속 부분수열의 개수를 구합니다.

제약
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000,000
각 원소는 1 이상 1,000 이하인 자연수

예시
N = 5, M = 5
배열 = 1 3 1 2 3

정답 구간
[1, 3, 1]
[2, 3]

출력
2

이 문제에서 가장 중요한 조건은 원소가 모두 양수라는 점입니다. 오른쪽에 원소를 더하면 합은 반드시 커지고, 왼쪽 원소를 빼면 합은 반드시 작아집니다. 이 단조성 덕분에 이미 지나온 시작점을 다시 확인하지 않아도 됩니다.

연속 부분수열은 원소를 건너뛰지 않습니다. 시작 인덱스와 끝 인덱스를 고르면 그 사이 원소를 모두 포함한 하나의 구간이 됩니다. 부분집합이나 일반 부분수열 문제와 구분해야 합니다.

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 예제 이동 추적표

right	추가한 값	M 초과 조정	조정 후 left·sum	누적 정답
0	1	없음	left=0, sum=1	0
1	3	없음	left=0, sum=4	0
2	1	없음	left=0, sum=5	1: [1, 3, 1]
3	2	1, 3을 차례로 제거	left=2, sum=3	1
4	3	1 제거	left=3, sum=5	2: [2, 3]

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

왜 정확하고 O(N)인가

정확성

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

시간과 공간

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

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

M	배열	기대값	확인 목적
5	[1, 3, 1, 2, 3]	2	본문 오류 회귀 테스트
6	[1, 2, 1, 3, 1, 1, 1, 2]	3	여러 길이의 정답 구간
3	[1, 1, 1, 1]	2	겹치는 구간
10	[1, 2, 3]	0	정답 없음
5	[5]	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을 사용해야 합니다.

FAQ

Q. while 조건은 sum > M인가요, sum >= M인가요?
이 글의 정확합 구현은 sum > M인 동안만 줄인 뒤 sum === M을 검사합니다. 합이 M인 창을 검사하기 전에 제거하지 않도록 실행 순서를 함께 봐야 합니다.

Q. 양수 배열에서 같은 right로 끝나는 정답이 왜 하나뿐인가요?
왼쪽 원소를 하나 뺄 때마다 합이 반드시 작아집니다. 따라서 특정 right에서 합이 M인 시작점이 하나 나오면 그보다 오른쪽 시작점의 합은 모두 M보다 작습니다.

Q. 배열에 0만 있어도 투 포인터를 그대로 쓰면 안 되나요?
0을 빼도 합이 변하지 않아 같은 right에 여러 정답 시작점이 생길 수 있습니다. 정확한 개수를 세려면 누적합 빈도 Map이 안전합니다.

Q. 구간 자체도 반환하려면 어떻게 하나요?
양수 풀이에서 합이 target일 때 [left, right]를 저장하면 됩니다. 다만 문제에서 개수만 요구하면 구간을 저장하지 않아야 추가 공간 O(1)을 유지할 수 있습니다.

함께 풀면 좋은 문제

• 정렬된 두 배열을 합치는 투 포인터 문제: 포인터가 뒤로 가지 않는 공통 원리를 비교합니다.
• 고정 길이 최대 매출 슬라이딩 윈도우: 창의 길이가 고정된 유형과 현재 가변 길이 유형을 구분합니다.

검증 기록: 2026-07-19, Node.js v24.15.0. 양수 5개와 0·음수 포함 4개 사례를 완전탐색 결과와 대조했습니다.