[LeetCode] 209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/description/?envType=study-plan-v2&envId=top-interview-150 

Minimum Size Subarray Sum - LeetCode

문제 유형 : 슬라이딩 윈도우

문제 난이도 : 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.

 

양수 배열 nums와 양수 target이 주어진다. 합이 target을 넘는 subarray의 최소 길이를 구하여라.

합이 target을 넘는 게 없다면, 0을 반환하라.

 

풀이

오른쪽과 왼쪽 포인터 변수를 만든다.

오른쪽 포인터를 계속 늘려가면서 sum에 누적시킨다.

만약 sum이 target보다 크거나 같다면, 최소길이를 업데이트시키고, 왼쪽 값부터 빼주면서 left도 값을 늘려 subarray의 길이를 줄인다.

 

right으로 윈도우를 확장시키고, left로 줄여나가는 방식이다.

 

최소길이 변수를 초기화할 때, 1e9 등의 큰 수로 초기화해준다.

 

코드

C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
       const int n = nums.size();
       int minLength =  1e9;

       int left = 0;
       int sum = 0;

       for(int right = 0; right < n; right++) {
           sum += nums[right];

           while(sum >= target) {
               minLength = min(minLength, right - left + 1);
               sum -= nums[left];
               left++;
           }
       }

       return minLength == 1e9? 0 : minLength;
    }
};

 

Python3

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        minLength = 1e9
        left = 0
        sum_val = 0

        for right in range(n):
            sum_val += nums[right]

            while sum_val >= target:
                minLength = min(minLength, right-left+1)
                sum_val -= nums[left]
                left += 1

        if minLength == 1e9:
            return 0
        
        return minLength

 

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int sum = 0;
        int minLength = (int)1e9;
        int left = 0;

        for(int right = 0; right < n; right++) {
            sum += nums[right];

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

        return minLength == 1e9? 0 : minLength;
    }
}