# 209. Minimum Size Subarray Sum

[](https://hackmd.io/AYgQ5p_RSPiUOonwbhwxuQ)

###### tags: `Leetcode` `Medium`

Source: [:link:][leetcode link]

[leetcode link]:
https://leetcode.com/problems/minimum-size-subarray-sum/

Average Rating：:star::star::star::star:

## Question Description

:::info
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.

:::

**Example 1**

Input: target = 4, nums = [1,4,4]
Output: 1

**Example 2**

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

**Constraints:**

* 1 <= target <= $10^9$
* 1 <= nums.length <= $10^5$
* 1 <= nums[i] <= $10^5$

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

## Question Explanation

***English Version***
For this question, we are expected to find the minimal length of sub-array, which has to be ==contiguous==, and can be larger than the `target` instead of equal to the `target` only.

For this question, brute-force is not a wise choice. We should try ==sliding window== which can also be called two-pointers method.

:pushpin:*Algorithm:*

* We have two pointers, `left` and `right`
* Then we change the position of these two pointers until the right pointer reaches the tail of the array
* `left pointer` = `0`, `right` = `left +1`
* move `right` to the tail of the array
* once the `sum` of `array[left,right]` >= target
* `left +1`
* store the length of each sub-array found
* return the min length of the sub-array


***Chinese Version***

滑动窗口的核心是明确以下几点：
* 窗口内是什么？
* 如何移动窗口的起始位置？
* 如何移动窗口的结束位置？

首先， 满足形成窗口的条件是，窗口内`value`的`和 >= target`. 此时窗口内就是一个符合题目要求的sub-array.

起始位置left移动的条件：当前`sum>=target`
结束位置移动的条件：`right`其实就是一个遍历array的指针

整个算法结束的标志：**`left`遍历完整个array**

:::warning
**主要逻辑**：

如果当前位置下滑动窗口里的值>target，那么缩小一下窗口，再往右划

:::

## Code

:::success

Python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        
        minlen = float('inf')
        left = 0
        right = 0
        curSum = 0
        
        while right < len(nums):
            curSum += nums[right]
            
            while curSum >= target:
                minlen = min(minlen, right - left + 1)
                curSum -= nums[left]
                left += 1
            
            right += 1
        
        return 0 if minlen == float('inf') else minlen

:::

Python: same as above

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if sum(nums)==target:
            return len(nums)
        if sum(nums)<target:
            return 0
        left,right,tot=0,0,0
        m=len(nums)
        for right in range(len(nums)):
            tot+=nums[right]
            while tot>=target:
                m=min(m,right-left+1)  #storing minimum length of such subarrays 
                tot-=nums[left]
                left+=1
                
        return m

## Linked Questions

904
76

## Q&A