LeetCode 209. Minimum Size Subarray Sum

hwibaski·2023년 8월 29일

leetcode ps

ps

목록 보기

9/12

209. Minimum Size Subarray Sum

문제

주어진 양의 정수 배열(nums)과 양의 정수(target)가 있을 때, 합이 target 이상인 부분 배열의 최소 길이를 반환하십시오. 만약 그러한 부분 배열이 없으면 대신 0을 반환하십시오.

부분 배열은 배열 내에서 연속적이며 비어있지 않은 요소들의 시퀀스입니다.

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

1차 시도 (1시간 10분 소요) - 실패 : 시간 초과

sliding window를 이용한다

target = 7
nums = [2,3,1,2,4,3]

1.
[2], [3], [1], [2], [4], [3]이 target과 같은지 확인

2. 
[2,3], [3,1], [1,2], [2,4], [4,3]이 target과 같은지 확인

3. 
[2,3,1], [3,1,2], [1,2,4], [2,4,3]이 target과 같은지 확인

4. 
[2,3,1,2], [3,1,2,4], [1,2,4,3]이 target과 같은지 확인

5. 
[2,3,1,2,4], [3,1,2,4,3]이 target과 같은지 확인

6. 
[2,3,1,2,4,3]이 target과 같은지 확인

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int answer = 0;
        
        for (int i = 1; i <= nums.length; i++) {
            int lt = 0;
            int rt = 0;
            int sum = 0;
            
            // 우선 i번째 까지의 합을 1차적으로 구해놓는다.
            while(rt < i) {
                sum += nums[rt];
                rt++;
            }
			
            // 이 때 구한 값이 target보다 크거나 같을 수 있으므로 확인한다.
            if (sum >= target) {
                answer = i;
                return answer;
            }

			// rt 포인터를 하나씩 증가시키고 그 값을 sum에 더한다. 그리고 lt 포인터 역시 하나씩 증가시키고 그 값을 sum에서 뺀다.
            while (rt < nums.length) {
                sum += nums[rt];
                rt++;
                sum -= nums[lt];
                lt++;

                // 이 때의 sum이 target 보다 크거나 같은지 확인한다.
                if (sum >= target) {
                    answer = i;
                    return answer;
                }
            }
        }

        return answer;
    }
}

2차 시도 - 실패(모범 답안 참고)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int lt = 0;
        int sum = 0;
        int answer = Integer.MAX_VALUE;

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

            while (sum >= target) {
                answer = Math.min(rt - lt + 1, answer);
                sum -= nums[lt];
                lt++;
            }
        }

        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
}

내가 생각한 슬라이딩 윈도우와 모범 답안의 슬라이딩 윈도우의 차이점이 있다. 내가 생각한 슬라이딩 윈도우는 윈도우의 크기가 고정되어 있다. 배열 한 개의 크기만큼 윈도우 크기를 설정하고 모든 배열을 반복하고, 배열 두 개의 크기만큼 윈도우 크기를 설정하고 모든 배열을 반복한다. 물론 모든 경우의 수를 찾는 것보다는 수행횟수가 줄어들었지만 여전히 많은 연산을 수행한다.

모범 답안의 슬라이딩 윈도우는 조금 다르다. 필요에 따라서 유동적으로 윈도우의 크기를 조절한다. 아래의 그림을 살펴보면 차이가 있다.