[LeetCode/Top Interview 150] [Sliding Window] 209. Minimum Size Subarray Sum

문제 링크: https://leetcode.com/problems/minimum-size-subarray-sum/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

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 <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

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)).

전략:

양수 값을 가지는 정수배열과 양수값을 가지는 타겟이 주어지고, 부분배열의 요소들의 합이 타겟 이상의 값을 가지는 부분배열의 최소 길이를 리턴한다. (없다면 0 리턴)

추가사항: O(n)의 복잡도를 가지는 답을 찾았다면 O(n log(n))의 시간복잡도를 가지는 답도 찾아보자.

부분배열(슬라이딩 윈도우)의 크기가 미리 정해져 있지 않고, 조건을 만족하는 부분배열 중 최소의 길이를 리턴하는 것이 목표다.

-> 먼저 0번째 요소만 있는 부분배열부터 시작해서 부분배열의 합이 타겟보다 작다면 점점 부분배열의 크기를 키우고, 타겟 이상이 되었다면 부분배열의 앞쪽부터 제거하여 여전히 타겟보다 큰지 확인한다.
타겟보다 더 이상 크지 않은 시점이 오면 다시 배열의 뒤쪽으로 부분배열을 이동하고, 이를 배열의 끝에 닿을 때까지 반복한다. -> 투포인터

코드 구현:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int start = 0;
        int sum = 0;
        int cnt = Integer.MAX_VALUE;
        
        // 배열 길이가 1인 경우 및 첫번째 요소가 조건을 만족시키는 경우를 빠르게 체크하기 위해서 단 하나 있는 요소가 타겟보다 크다면 즉시 1 리턴
        if (target <= nums[0]) {
            return 1;
        }
            
        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];       
            while (target <= sum) {
                cnt = Math.min(cnt, -start + end + 1);
                sum -= nums[start++];
            } 
        }
        if (cnt == Integer.MAX_VALUE) {
            cnt = 0;
        }
        return cnt;
    }
}

실행결과:
Time: 1 ms (99.96%), Space: 54.1 MB (79.83%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0209-minimum-size-subarray-sum/0209-minimum-size-subarray-sum.java

개선 방안(실패):

우선 지금 방식은 O(n)의 시간 복잡도를 가지므로 O(nlog(n))의 복잡도를 가지는 슬라이딩 윈도우 방식을 찾아봐야겠다.
전체 배열 길이의 절반 길이를 크기로 가지는 슬라이딩 윈도우로 조건이 맞는지 확인하고, 맞는다면 다시 그 절반의 길이를 가진 부분배열로 재귀적으로 반복, 조건이 맞지 않다면 슬라이딩 윈도우의 크기를 +1 키워서 다시 테스트.
--> 내가 구현한 결과로는 개별적인 테스트 케이스는 통과하지만 시간초과가 발생함

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int size = n/2; // 초기 슬라이딩 윈도우 크기
        int sum = 0;
        int answer = Integer.MAX_VALUE;
        if (target <= nums[0]) {
            return 1;
        }
        
        while (size > 1 && size < n) {
            // 슬라이딩 윈도우 사이즈 결정
            if (sum < target) { // 타겟보다 작다면 사이즈 증가
                size++;
            } else { // 타겟 이상이라면 사이즈 절반으로
                answer = Math.min(answer, size);
                size = size / 2;
            }
            
            sum = 0;        
            // 초기 부분배열 요소의 값의 합
            for (int i=0;i<size;i++) {
                sum += nums[i];
            }
            
            // 배열 0번 위치부터 슬라이딩 윈도우 이동
            for (int i=0;i<n-size+1;i++) {
                // 가장 왼쪽 요소를 1개 빼고
                sum-=nums[i];
                // 부분 배열 바깥 바로 오른쪽의 요소를 1개 추가
                sum+=nums[i+size-1];
                if (sum >= target) {
                    answer = Math.min(answer, size);
                    continue;
                }
            }
        }
        
        // 부분배열의 길이가 1이거나 전체 배열의 길이인 엣지케이스
        int all_sum = 0;
        for (int i=0;i<n;i++) {
            if (nums[i]>=target) {
                return 1;
            }
            all_sum += nums[i];
        }
        if (all_sum < target) {
            answer = 0;
        }
        return answer;
    }
}
Time Limit Exceeded	(실패)

Discuss 탭의 타인 코드:

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i = 1, j = nums.length, min = 0;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (windowExist(mid, nums, s)) {
                j = mid - 1;
                min = mid;
            } else i = mid + 1;
        }
        return min;
    }


    private boolean windowExist(int size, int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i >= size) sum -= nums[i - size];
            sum += nums[i];
            if (sum >= s) return true;
        }
        return false;
    }
}
Time: 4 ms (7.03%), Space: 53.5 MB (97.52%) - LeetHub

회고:

이 문제의 경우 입력의 크기 차이 때문에 nlogn의 시간 복잡도를 가지는 코드보다도 처음에 구현한 그냥 투 포인터가 더 빠른 결과가 나온 것 같다.
내 코드를 nlogn으로 개선해보고자 했었는데 방향은 맞았지만 구현 방식이 잘못되어 시간초과가 발생했다.
결국 찾아본 다른 사람의 정답코드는 탐색하고자 하는 지점을 투포인터로 정하고, 그 내부를 탐색 지점의 절반의 길이를 가진 슬라이딩 윈도우로 답이 나오는지 확인하고, 답이 나온 경우 다시 탐색 범위를 좁혀 반복하는 뒤 min값을 리턴하는 방식이다.
가장 큰 차이는 탐색 지점을 좁힌 부분이었던 것 같다.