← 12주차 · 체크포인트 2
보통슬라이딩 윈도우투 포인터

합이 target인 최단 구간

양의 정수 배열 nums와 정수 target이 주어져요. 연속한 원소들의 합이 정확히 target이 되는 구간 중 가장 짧은 것의 길이를 반환해요. 그런 구간이 하나도 없으면 0을 반환해요.

모든 값이 양수라서, 구간을 오른쪽으로 넓히면 합이 커지고 왼쪽을 줄이면 합이 작아져요. 이 성질 덕분에 포인터 두 개로 한 번만 훑어서 O(n)에 풀 수 있어요.

예시

예시 1
입력
nums = [1, 2, 3, 7, 5], target = 12
출력
2
설명
[7, 5]의 합이 12이고 길이가 2예요. 더 짧은 구간은 없어요.
예시 2
입력
nums = [1, 1, 1, 1], target = 3
출력
3
설명
연속한 1 세 개의 합이 3이에요.
예시 3
입력
nums = [1, 2, 3], target = 7
출력
0
설명
합이 정확히 7인 연속 구간이 없어요.

제한 사항

  • 1 ≤ nums.length ≤ 100,000
  • 1 ≤ nums[i] ≤ 10,000
  • 1 ≤ target ≤ 1,000,000,000
왼쪽 포인터를 두고 오른쪽으로 창을 넓혀요. 창의 합이 target을 넘으면 왼쪽을 줄여 합을 낮춰요. 합이 정확히 target인 순간마다 창의 길이를 최솟값 후보로 기록해요.
javascript
function shortestSubarraySum(nums, target) {
  let left = 0;
  let sum = 0;
  let best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum > target && left <= right) {
      sum -= nums[left];
      left++;
    }
    if (sum === target) best = Math.min(best, right - left + 1);
  }
  return best === Infinity ? 0 : best;
}
이전 문제회의 시간 겹침 판정
다음 문제체육복 나눠주기
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.