[Dart/LeetCode 209] Minimum Size Subarray Sum — 슬라이딩 윈도우 알고리즘으로 푸는 최단 부분합 문제

부분합이 특정 값을 넘는 가장 짧은 연속된 부분 배열의 길이를 구하는 문제입니다.
단순히 합만 구하는 것이 아니라, 길이까지 고려해야 하기에 효율적인 알고리즘이 필요합니다.
이 글에서는 Brute-force 접근 → 슬라이딩 윈도우 최적화 과정을 거쳐,
Dart로 완성도 높은 코드를 작성하고 이해하는 과정을 함께합니다.

---

📘 문제 설명

양의 정수 배열 nums와 목표값 target이 주어질 때,
합이 target 이상이 되는 연속된 부분 배열(subarray) 중에서
가장 짧은 길이를 반환하라.
없으면 0을 반환한다.

---

❌ Brute-force 접근 (비효율)

int minLength = nums.length + 1;

for (int i = 0; i < nums.length; i++) {
  int sum = 0;
  for (int j = i; j < nums.length; j++) {
    sum += nums[j];
    if (sum >= target) {
      minLength = min(minLength, j - i + 1);
      break;
    }
  }
}

• 시간복잡도: O(n²) → 큰 입력에서는 시간 초과 가능성 있음
• 매 i마다 전체 탐색 → 비효율적

---

✅ 최적화: 슬라이딩 윈도우

슬라이딩 윈도우는 합이 기준 이상일 때 길이를 최소화하는 문제에 딱 적합합니다.

---

💻 Dart 코드

class Solution {
  int minSubArrayLen(int target, List<int> nums) {
    int n = nums.length;
    int left = 0;
    int sum = 0;
    int minLength = n + 1;

    for (int right = 0; right < n; right++) {
      sum += nums[right];

      while (sum >= target) {
        minLength = minLength < (right - left + 1) ? minLength : (right - left + 1);
        sum -= nums[left];
        left++;
      }
    }

    return minLength == n + 1 ? 0 : minLength;
  }
}

 

---

🧠 코드 풀이

구간 설명

sum += nums[right]	윈도우 오른쪽 확장하며 합 누적
while (sum >= target)	조건 만족 시 길이 갱신 시도
minLength = ...	현재 길이가 기존 최소보다 짧으면 갱신
sum -= nums[left]; left++	왼쪽을 줄이며 더 짧은 조합 시도
종료 후 리턴	조건 만족한 적 없으면 0, 있으면 최소 길이

---

🌊 슬라이딩 윈도우 흐름 예시

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

step	left	right	sum	조건 만족	윈도우 길이	minLength
1	0	0	2	❌	-	∞
2	0	1	5	❌	-	∞
3	0	2	6	❌	-	∞
4	0	3	8	✅	4	4
5	1	3	6	❌	-	4
6	1	4	10	✅	4	4 → 3
7	2	4	7	✅	3	3 → 2
8	3	4	4	❌	-	2
9	3	5	7	✅	3	유지
10	4	5	3	❌	-	2

---

⏱ 시간 & 공간 복잡도

항목 복잡도 설명

시간	O(n)	각 포인터가 최대 한 번씩만 이동
공간	O(1)	추가 공간 없음

---

✨ 실전 팁 요약

• “조건 만족하는 최소 길이” 문제는 무조건 슬라이딩 윈도우 먼저 떠올릴 것
• 오른쪽으로 확장하면서 합을 만들고, 왼쪽을 줄여가며 최소 길이 갱신
• 투 포인터 + 조건 기반 줄이기 전략은 여러 문제에 응용 가능

LeetCode, Dart 알고리즘, 슬라이딩 윈도우, 투 포인터, 부분합 문제