209. Minimum Size Subarray Sum

난이도: 중간 (Medium)

링크: LeetCode 209

풀이 날짜: 2025/10/19(못품)

 

1. 문제 이해

양의 정수 배열 nums와 정수 target이 주어질 때, 연속된 부분 배열(subarray)의 합이 target 이상이 되는 가장 짧은 길이를 구하는 문제다. 만약 조건을 만족하는 부분 배열이 없다면 0을 반환한다.

 

2. 접근 방식 — Sliding Window (슬라이딩 윈도우)

이 문제는 모든 부분 배열을 검사하면 O(n²) 시간이 걸리므로 비효율적이다. 대신 슬라이딩 윈도우(Sliding Window) 개념을 사용하면 O(n)에 해결할 수 있다. 핵심 아이디어는 다음과 같다.

 

“합이 target 이상이 될 때마다, 왼쪽 포인터를 최대한 오른쪽으로 이동시켜 최소 길이를 찾는다.”

 

즉,

• 오른쪽 포인터(right)는 윈도우를 확장하면서 sum을 누적한다.
• 누적합이 target 이상이 되면, 왼쪽 포인터(left)를 당겨 윈도우를 줄인다.
• 이때의 길이 (right - left + 1)이 최소값 후보가 된다.

이 과정을 반복하면 모든 가능한 최소 길이를 효율적으로 찾을 수 있다.

 

3. 풀이 코드

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {    
  let left = 0;
  let sum = 0;
  let minLength = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      minLength = Math.min(minLength, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }

  return minLength === Infinity ? 0 : minLength;
};

 

이 문제의 포인트는 “조건을 만족하면 윈도우를 줄인다”는 발상이다.

• sum이 target 이상이 되는 순간, 이미 조건을 만족했기 때문에 더 이상 right를 확장할 필요가 없다.
• 오히려 left를 오른쪽으로 움직이며 가능한 한 구간을 줄여야 “최소 길이”를 찾을 수 있다.
• 이렇게 하면 불필요한 중복 계산 없이 효율적으로 최적 해를 구할 수 있다.

예시 시나리오

입력: target = 7, nums = [2,3,1,2,4,3]

단계	left	right	sum	minLength	설명
1	0	0	2	∞	아직 target 미만
2	0	1	5	∞	아직 target 미만
3	0	2	6	∞	아직 target 미만
4	0	3	8	4	sum ≥ 7 -> 길이 4 저장
5	1	3	6	4	sum < 7 -> left 이동 중단
6	1	4	10	4	sum ≥ 7 -> 길이 4
7	2	4	7	3	left 이동 -> 길이 3 갱신
8	3	4	6	3	sum < 7
9	3	5	9	3	sum ≥ 7 -> 길이 3 유지
10	4	5	7	2	left 이동 -> 최소 길이 2로 갱신 ✅

최종 결과 -> 2

시간 및 공간 복잡도

항목	복잡도	설명
시간 복잡도	O(n)	left, right 포인터가 각각 한 번씩 이동
공간 복잡도	O(1)	상수 개의 변수만 사용

 

4. 핵심 정리

개념	설명
문제 유형	Two Pointers, Sliding Window
핵심 아이디어	합이 target 이상일 때마다 윈도우를 줄이며 최소 길이 갱신
핵심 변수	left, right, sum, minLength
시간 복잡도	O(n)
공간 복잡도	O(1)
포인트	“조건을 만족하면 윈도우를 줄인다.” — 최소 길이를 찾는 핵심 패턴