[LeetCode] 209. Minimum Size Subarray Sum

Minimum Size Subarray Sum - LeetCode

양의 정수 배열이 주어지면 배열의 조합의 합이 target과 같아야 하고

target과 같은 조합중 가장 작은 조합의 길이를 반환하는 문제입니다.

 

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:

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

 

문제 접근

배열의 요소를 확인하는 문제이니 투포인터를 이용해서 접근을 시도해보았습니다.

 

하지만 정확히 풀어내지 못하였고 검색을 통하여 풀이법을 파악할 수 있었습니다. 

 

실패코드

public int minSubArrayLen(int target, int[] nums) {
        int start = 0;
        int end = nums.length-1;
        int sum = nums[start] + nums[end];
        int length = 2;

        ArrayList<Integer> candidates = new ArrayList<>();
        while (start <= end) {
            if (nums[start] == target || nums[end] == target) {
                System.out.println("JackPot!");
                return 1;
            }

            if (sum == target) {
                start++;
                if (start < nums.length) {
                    sum = nums[start] + nums[end];
                }
                candidates.add(length);
                length = 2;
            }
            else if (sum > target) {
                length = 2;
                end--;
                if (end >= 0) {
                    sum = nums[start] + nums[end];
                }
            }
            else if (sum < target) {
                length += 1;
                start++;
                if (start < nums.length) {
                    sum += nums[start];
                }
            }
        }
        System.out.println(candidates);
        if (candidates.isEmpty()) {
            return 0;
        }
        Collections.sort(candidates);

        return candidates.get(0);
    }

 

다른사람의 풀이

슬라이딩 윈도우를 사용한 풀이입니다.

두개의 요소를 선택해서 해결하는 로직이 아닌 여러개 범위의 요소들을 선택해야하기 때문에 슬라이딩 윈도우를 사용해야합니다.

 

min : 최소 길이를 구하기 위한 변수

left, right : 범위를 확인하기 위한 변수

sum : target과 비교하여 정답을 도출하기 위한 변수

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

    }

 

시간복잡도

right가 nums.length의 길이까지 반복하므로 O(n)의 시간복잡도가 필요합니다.

 

 

느낀점

투포인터와 슬라이딩 윈도우의 차이점을 알고 잘 활용해야겠습니다.

2개의 요소를 필요하다면 투포인터

2개 이상이고 연속된 배열의 요소가 필요하다면 슬라이딩 윈도우를 사용해야겠습니다.

 

참고

https://leetcode.com/problems/minimum-size-subarray-sum/solutions/1769644/JAVA-99-O(N)-solution-Sliding-window-(With-visualization/