Leetcode - 209. Minimum Size Subarray Sum

문제

sub-array의 합이 주어진 target보다 크거나 같은 sub-array의 최소 길이는? (없다면 0 리턴)

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.

해결 아이디어

전형적인 슬라이딩 윈도우 전략

• if (sum >= target) -> st++
  앞부분 사이즈 줄이기
• if (sum < target) -> end++
  뒷부분 사이즈 늘리기

풀이 O(n)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // if greater, size down by begin
        // if smaller, size up by last
        int st = 0;
        int end = 0;
        int sum = nums[st];
        int len = 1;
        int minlen = nums.size();
        
        
        while (st <= end && end < nums.size()) {
            
            if (sum >= target) {
                minlen = std::min(len, minlen);
                
                if (st == end) {
                    st++;
                    end++;
                    sum = nums[st];
                } else {
                    sum -= nums[st++];
                    len--;
                }
            } else {
                end++;
                if (end >= nums.size())
                    break;
                sum += nums[end];
                len++;
            }
        }
        if (st == 0 && end >= nums.size() && sum < target)
            return 0;
        return minlen;
    }
};

230318 다시 풀어봄. 논리적으로 보다 간결한 로직.

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int right = 0;
        int sum = nums[left];
        int minlen = INT_MAX;
        int len = 1;
        
        while (right < nums.size() && left <= right) {
            if (sum < target) {
                if (right == nums.size() -1)
                    break;
                sum += nums[++right];
                len++;
            } else {
                minlen = std::min(minlen, len);
                sum -= nums[left++];
                len--;
            }
        }
        return (minlen == INT_MAX) ? 0 : minlen; 
    }
};