LeetCode 209 - Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum

 

subarray의 합이 target보다 크거나 같은 subarray 중 최소 길이를 구하라.

subarray이기에 정렬이 수행되면 안 된다.

 

연속된 수를 확인할 때는 슬라이딩 윈도 기법이 좋다.

여기서 슬라이딩 윈도의 크기를 조절하며 최소 길이를 갱신하는 방법을 쓰면 될 것 같다.

 

이 슬라이딩 윈도는 두 개의 포인터로 구성이 돼있다.

두 포인터 사이에 있는 값들의 합이 target보다 크면 최소 길이를 갱신한다. 하지만 최소를 구해야 하기 때문에 범위를 줄여가며 체크를 해줘야 한다.

따라서 왼쪽 범위를 하나 줄이고 다시 체크를 하는 동작을 반복한다.

그러다가 target보다 합이 작아져 더 이상 왼쪽을 줄일 수 없을 때 오른쪽 범위를 늘려주도록 한다.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;

        for (int 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 == Integer.MAX_VALUE ? 0 : minLength;
    }
}