Leet_209_Minimum Size Subarray Sum

걸린 시간: 20m

알고리즘 분류: 슬라이딩 윈도우

슬라이딩 윈도우 알고리즘의 대표적인 문제입니다.

완전탐색을 통한 모든 경우의 수를 계산하여 길이를 구하는 것은 상당한 비효율이 발생하기때문에 left 포인터를 하나 두어 right포인터와의 길이를 갱신하는 방식으로 설계하여 해결하여 시간복잡도를 줄여나가는 방식으로 해결하였습니다.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0, sum = 0;
        int result = n + 1; 
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];

            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        
        return result == n + 1 ? 0 : result;
    }
}