[LeetCode] 209. Minimum Size Subarray Sum - Java

Minimum Size Subarray Sum - LeetCode

 

문제

Given an array of positive integers nums and a positive integer target, return the minimal length of a 

subarray

 whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

 

Constraints:

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

 

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

 

양의 정수 배열이 주어질 때 합이 target 보다 크거나 같은 하위 배열의 최소 길이를 반환하는 문제이다.

조건을 만족하는 하위 배열이 없으면 0을 반환한다.

 

---

 

내 풀이

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length -1;
        int minLength = Integer.MAX_VALUE;

        int start = 0 ;
        int end = 0;
        int sum = nums[0];
        while(start <= n){

            if(sum >= target){
                minLength = Math.min(minLength, end-start+1);
            }

            if(end == n){
                sum -= nums[start];
                start++;
                continue;
            }

            if(sum > target){
                sum -= nums[start];
                start++;
            }else{
                end++;
                sum += nums[end];
            }

        }

        if(minLength == Integer.MAX_VALUE) minLength = 0;

        return minLength;        
    }
}

 

슬라이딩 윈도우

start 와 end 0에서부터 시작해 조건에 따라 배열 범위를 움직이며 합을 구하고 target 과 비교하며 범위의 최단길이를 업데이트해준다.

end와 start 가 배열 요소의 개수 n 에 도달할 때까지 반복하는 흐름으로 코드를 작성했다.

마지막으로 최단길이가 처음 초기화한 최대정수값 그대로라면, 합이 target 보다 큰 경우가 없으므로 0을 반환해준다.

 

• 시간복잡도 : O(n) - 배열의 각 요소를 한 번씩만 처리한다
• 공간복잡도 : O(1)

 

시간복잡도와 공간복잡도는 잘 고려해서 푼 것 같지만 코드가 뭔가 지저분하다는 느낌이 들었다.

for문 안에 조건문들을 좀 더 줄이거나 합칠 수 있지 않을까 생각했다.

 

---

 

다른 사람의 풀이

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

        int start = 0 ;
        int sum = 0;

        for(int end = 0; end<nums.length; end++){
            sum +=  nums[end];

            while(sum >= target){
                minLength = Math.min(minLength, end-start+1);
                sum -= nums[start];
                start++;
            }
        }

        if(minLength == Integer.MAX_VALUE) minLength = 0;

        return minLength;        
    }
}

똑같이 슬라이딩 윈도우를 사용해 풀었지만 코드가 훨씬 간결하다.

나는 start 와 end 가 모두 n에 도달해야 했기 때문에 조건이 길어졌지만, 이 코드는 end 범위를 0 ~ n 까지 설정한 for문 안에서 start 를 움직이는 것이기 때문에 매우 간단해졌다.

 

반복문의 범위와 조건 설정에 대해 최선의 방법이 무엇일까 고민하는 과정은 알고리즘을 풀이할 때 매우 중요한 과정인 것 같다.