209 - Minimum Size Subarray Sum

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

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

A subarray is a <mark style="background: #FFB86CA6;">contiguous</mark> non-empty sequence of elements within an array.

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

#include <climits> 
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0, min_length = INT_MAX, temp_length = 0, i = 0;
        for ( int j = 0; j < nums.size(); j++ ) {
            sum += nums[j];
            temp_length++;
            if ( sum >= target ) {
                for ( i; sum >= target; i++ ) {
                    if ( temp_length < min_length ) min_length = temp_length;
                    sum -= nums[i];      
                    temp_length--;    
                }

            }
        }

        if ( min_length == INT_MAX ) return 0;
        else return min_length;
    }
};

滑動窗口:
i => 內部滑動窗口
j => 外部滑動窗口

#include <climits> 
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // sliding windows (subarray是連續的)
        int result = INT_MAX;
        int cur_length = 0, cur_sum = 0, left = 0;
        for ( int right = 0; right < nums.size(); right++ ) {
            cur_length++;
            cur_sum += nums[right];
            while ( cur_sum >= target ) {
                if ( cur_length < result ) result = cur_length;
                cur_sum -= nums[left];
                left++;
                cur_length--;
            }

        }

        if ( result == INT_MAX ) return 0;
        return result;
    }
};