# \[209]\[中等]\[滑动窗口] 长度最小的子数组

## 题目描述

[209. 长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum/)

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

示例:

```
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
```

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

## 解题思路

[解题思路: 长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/)

### 双指针

数组中**连续子序列**的问题一种常见的思路就是**滑动窗口**, 即**双指针**.

定义两个指针`start`和`end`, 分别指向子数组开始和结束的地方, 初始都为0. 将它们之间子数组中数字之和记为`sum`, 如果$$\text{sum} \ge s$$, 需要更新起始指针`start`, 直到对应的$$\text{sum} \lt s$$.

然后逐步移动`end`指针, 直到又出现$$\text{sum} \ge s$$, 然后重复上述步骤.

在这个过程中, 在每次$$\text{sum} \ge s$$时, 都比较子数组长度, 并记录最短子数组.

```python
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        start, end = 0, 0
        current, length = 0, n + 1
        while end < n:
            current += nums[end]
            while current >= s:
                length = min(length, end - start + 1)
                current -= nums[start]
                start += 1
            end += 1
        return 0 if length > n else length
```

### 前缀和

数组中**连续子序列**的问题另一种常见的思路**前缀和**.

要求:

* **数组中每个元素都为正, 前缀和序列一定是递增的, 这样查找的结果才是唯一的**

创建一个数组$$\text{sums}$$来存储数组的前缀和, 即$$\text{sums}\[i]$$表示从$$\text{num}\[0]$$到$$\text{num}\[i-1]$$之和.

对于下标$$i$$, 我们找到$$\text{sums}\[i] + s$$在$$\text{sums}$$中的位置$$\text{bound}$$, 这样从$$i$$开始到$$\text{bound}-1$$位置$$\text{num}$$中所有数之和为$$s$$, 对应的子序列长度为$$\text{bound}-i$$.

边界条件为$$\text{bound}-1$$必须小于$$\text{sums}$$的长度, 即小于$$\text{len}(\text{num})+1$$, 这样才能在$$\text{sums}$$中去到值.

```python
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0

        n = len(nums)
        ans = n + 1
        sums = [0]
        for i in range(n):
            sums.append(sums[-1] + nums[i])  # `sums`最终的长度为`n+1`

        for i in range(n):
            target = s + sums[i]
            bound = bisect.bisect_left(sums, target)
            if bound != len(sums):
                ans = min(ans, bound - i)

        return 0 if ans == n + 1 else ans
```


---

# Agent Instructions: 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://kerasnoone.gitbook.io/garnet/suan-fa/hua-dong-chuang-kou/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.