# \[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
```