# 主題: 209. Minimum Size Subarray Sum
---
###### tags: `leetcode`
## 定洲整理

---
## 題目大要:
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [ numsl, numsl+1, ..., numsr-1, numsr ] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

給定一個含有 n 個正整數的 array 和一個正整數 target 。

找出該array中滿足其和 ≥ target 的長度最小的連續 sub array [numsl, numsl+1, ..., numsr-1, numsr] ，return回傳長度。如果不存在符合條件的sub array，return 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

Constraints:

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

---
## 解法(演算法):

<sol.1> 暴力解
* 時間複雜度：$O(n^2)$
* 空間複雜度：$O(1)$

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT_MAX;
        int sublength = 0;
        int sum = 0;
        for(int i=0;i<nums.size();i++){
            sum = 0;
            for(int j=i;j<nums.size();j++){
                sum += nums[j];
                if(sum>=target){
                    sublength = j-i+1; //計算sub array 長度
                    //result = (result < sublength) ? result : sublength;
                    if(result>=sublength){ //如果subarray比result小，則取代result
                        result = sublength;
                    }
                    break;
                }

            }
        }
        if(result==INT_MAX) //result 沒變過 ， 回傳 0
            return 0;
        else
            return result;
     }
};

<sol.2> Sliding Window 滑動窗口
* 時間複雜度：$O(n)$
* 空間複雜度：$O(1)$

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0;
        int i = 0;
        int subLength = 0;
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            while (sum >= s) { //>=target(s)，i++；<target(s)，j++
                subLength = (j - i + 1);
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // sum - sum[i] , i++
            }
        }
        return result == INT32_MAX ? 0 : result;
    }
};


---
## 程式碼(C++)

<sol.1> 暴力解
* 時間複雜度：$O(n^2)$
* 空間複雜度：$O(1)$

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT_MAX;
        int sublength = 0;
        int sum = 0;
        for(int i=0;i<nums.size();i++){
            sum = 0;
            for(int j=i;j<nums.size();j++){
                sum += nums[j];
                if(sum>=target){
                    sublength = j-i+1; //計算sub array 大小
                    //result = (result < sublength) ? result : sublength;
                    if(result>=sublength){ //如果subarray比result小，則取代result
                        result = sublength;
                    }
                    break;
                }

            }
        }
        if(result==INT_MAX) //result 沒變過 ， 回傳 0
            return 0;
        else
            return result;
     }
};

<sol.2> Sliding Window 滑動窗口
* 時間複雜度：$O(n)$
* 空間複雜度：$O(1)$

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0;
        int i = 0;
        int subLength = 0;
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            while (sum >= s) {
                subLength = (j - i + 1);
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // sum - sum[i] , i++
            }
        }
        return result == INT32_MAX ? 0 : result;
    }
};