# 209. 长度最小的子数组

<https://leetcode-cn.com/problems/minimum-size-subarray-sum/>

## 解法一：双指针法

i，j两重循环暴力超时，因此不可取。

left记录左边界，i向右遍历数组，依次累加，当sum>=s时left每次右移一位，并计算最小长度，直到sum\<s为止。

```python
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        n = len(nums)
        minSize = n+1    #取一个不能到达的数即可，不一定要sys.maxsize
        left = 0    #左边界
        sum = 0    #left到i的累加和
        for i in range(n):
            sum += nums[i]
            while sum >= s:
                minSize = min(minSize, i-left+1)
                sum -= nums[left]
                left += 1
        #若min还是n+1说明没找到
        return 0 if minSize == n+1 else minSize
```

## 解法二：二分

用sums\[i]表示序列\[0...i-1]的和，因为每个都是正数，因此sums是递增序列，可以用二分（只有这里沾点边，其实这题跟二分没有太大联系），则序列\[i...k]的和为sums\[k]-sums\[i-1]。 思路：每个i（0\~n-1）要找一个k，使得sums\[k]-sums\[i-1] >= target，且要求\[i...k]长度最小，因此k尽可能小，即取等号sums\[k] = target + sums\[i-1]。用二分在sums找对应的k，此时序列长度=k-i+1。每次迭代更新最短长度

```python
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        minLen = n + 1
        sums = [0]
        #计算求和数组sums
        for i in range(0, n):
            sums.append(sums[-1] + nums[i])
        #从1开始遍历sums
        for i in range(1, n+1):
            t = sums[i-1] + target
            #在sums中二分查找t
            pos = bisect.bisect_left(sums, t)    
            if pos != n+1:    #pos为n说明sums中找不到t
                minLen = min(minLen, pos - i + 1)    #更新最短长度
        #minLen仍未n+1说明没找到
        return 0 if minLen == n+1 else minLen
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/201-400/209.-chang-du-zui-xiao-de-zi-shu-zu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.