###### tags: `Leetcode` `medium` `sliding window` `python` `c++`

# 209. Minimum Size Subarray Sum

## [題目連結:] https://leetcode.com/problems/minimum-size-subarray-sum/description/

## 題目:
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.

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

**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

## 解題想法:
* 題目為求數組中，連續子數組和>=target，且距離長度最短
* O(N):
* 使用sliding window:
* 標準SOP:
* head=0, tail=0, res, curSum=0
* curSum累加nums[tail]
* while判斷合法or不合法時的動作:
* curSum-nums[head]
* head往前
* tail往前
## Python:

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """#sum is greater than or equal to target
        #time: O(n)
        res=float('inf')
        curSum=0
        head=0
        tail=0
        while tail<len(nums):
            curSum+=nums[tail]
            while curSum>=target:
                res=min(res,tail-head+1)
                curSum-=nums[head]
                head+=1
            tail+=1
        return 0 if res==float('inf') else res

target = 7
nums = [2,3,1,2,4,4]
result = Solution()
ans = result.minSubArrayLen(target,nums)
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res=INT_MAX;
        int head=0, tail=0, curSum=0;
        while (tail<nums.size()){
            curSum+=nums[tail];
            while (curSum>=target){
                res=min(res, tail-head+1);
                curSum-=nums[head];
                head+=1;
            }
            tail+=1;
        }
        return (res==INT_MAX)? 0 : res;
    }
};

int main(){
    Solution* res=new Solution();
    vector<int> nums={2,3,1,2,4,4};
    int target=7;
    int ans=res->minSubArrayLen(target,nums);
    cout<<ans<<endl;
    return 0;
}

* O(N log(N)):
* 使用二分法找合適的位置
* 高手解析: [https://www.796t.com/article.php?id=69194]