[LeetCode] 209. Minimum Size Subarray Sum - Java[자바]

링크

문제

양의 정수 배열 nums와 양의 정수 target이 주어졌을 때, 합이 target보다 크거나 같은 서브 배열 의 최소 길이를 반환합니다. 그러한 서브 배열이 없으면 대신 0을 반환합니다.

풀이

• sliding window로 되어있길래, sliding window로 풀게되면 어떻게 될까를 고민했다.
  - 일단 크기가 동적으로 변해야 하는데 이게 sliding window가 맞나..? 싶었다.
  - 만약 sliding window로 풀게 된다면 길이가 1개인 배열부터 배열의 길이 까지 늘려가면서 찾아야 될 거라 생각했다.
  

Sliding Window 풀이

class Solution {  
  
    public int minSubArrayLen(int target, int[] nums) {  
        int left = 0;  
        int right = 0;  
        int minLength = Integer.MAX_VALUE;  
        int sum = 0;  
        while (right < nums.length) {  
            sum += nums[right++];  
            while (sum >= target) {  
                minLength = Math.min(minLength, right - left);  
                sum -= nums[left++];  
            }  
        }  
        if (minLength == Integer.MAX_VALUE) {  
            return 0;  
        }
				return minLength;   
    }  
}

동일 하지만, right를 for문으로 만든 코드입니다.

class Solution {  
    public int minSubArrayLen(int target, int[] nums) {  
        int n = nums.length;  
        int ans = Integer.MAX_VALUE;  
        int left = 0;  
        int sum = 0;  
        for (int i = 0; i < n; i++) {  
            sum += nums[i];  
            while (sum >= target) {  
                ans = Math.min(ans, i - left + 1);  
                sum -= nums[left++];  
            }  
        }  
        return (ans != Integer.MAX_VALUE) ? ans : 0;  
    }  
}

누적합을 이용한 풀이

class Solution {  
  
    public int minSubArrayLen(int target, int[] nums) {  
        int[] prefixSum = new int[nums.length + 1];  
        for (int i = 0; i < nums.length; i++) {  
            prefixSum[i + 1] = prefixSum[i] + nums[i];  
        }  
        int left = 0;  
        int right = 1;  
        int minLen = Integer.MAX_VALUE;  
        while (right < prefixSum.length) {  
            int sum = prefixSum[right] - prefixSum[left];  
            if (sum >= target) {  
                minLen = Math.min(minLen, right - left);  
                left++;  
            } else {  
                right++;  
            }  
        }  
        if (minLen == Integer.MAX_VALUE) {  
            return 0;  
        }  
        return minLen;  
    }  
}