[Leetcode][Java] 209 Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 

양수로 이루어진 배열 nums와 양수 integer target이 주어진다.

target보다 크거나 같은 연속적인 서브 배열의 길이를 구해라, 단 길이는 최소한이어야 한다.

만약 조건에 만족하는 서브 배열이 없는 경우에는 0을 반환하라.

---

주어진 배열에서 타겟보다 크거나 같은 서브 배열의 합의 길이를 구하는 문제이다.

해당 조건을 만족하는 여러개의 서브 배열이 존재할 수 있지만, 그중에서 가장 길이가 짧은 내역을 반환하면 된다. 

 

배열을 for문을 돌며 sum이 target보다 커지는 시점을 찾고,

해당 시점에서 idx가 0부터 sum을 빼며 길이를 짧게 하며 조건을 만족하는지 찾아보도록 하자.

중간중간 조건이 만족할 때마다, 해당 시점의 서브  배열의 길이를 체크하며 최솟값을 찾도록 하자.

 

    public int minSubArrayLen(int target, int[] nums) {

        int idx = 0;
        int rst = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];

            if (sum >= target) {
                // make shorter of idx
                rst = Math.min(rst, i - idx + 1);
                sum -= nums[idx];
                idx++;
                while (sum >= target) {
                    rst = Math.min(rst, i - idx + 1);
                    sum -= nums[idx];
                    idx++;
                }
            }
        }
        return rst == Integer.MAX_VALUE ? 0 : rst;
    }