# 209.长度最小的子数组 (Medium)

## 问题描述
[209. 长度最小的子数组 (Medium)](https://leetcode.cn/problems/minimum-size-subarray-sum/)

给定一个含有 `n` 个正整数的数组和一个正整数 `target` **。**

找出该数组中满足其和 `≥ target` 的长度最小的 **连续子数组** `[numsₗ, numsₗ+₁,
..., numsr-₁, numsr]` ，并返回其长度 **。** 如果不存在符合条件的子数组，返回 `0` 。

**示例 1：**

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

```

**示例 2：**

```
输入：target = 4, nums = [1,4,4]
输出：1

```

**示例 3：**

```
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

```

**提示：**

- `1 <= target <= 10⁹`
- `1 <= nums.length <= 10⁵`
- `1 <= nums[i] <= 10⁵`

**进阶：**

- 如果你已经实现 `O(n)` 时间复杂度的解法, 请尝试设计一个 `O(n log(n))` 时间复杂度的解法。

## 解题思路
### 滑动窗口
如果`sum < target`，`sum += nums[right++]`，即右指针右移，扩大窗口；否则更新`min_len`，`sum -= nums[left]`，左指针右移，缩小窗口

### 前缀和+二分
因为这里要考虑的是连续子数组的和，因此很容易想到**前缀和**，这里数组中的数都大于0，所以**前缀和**数组单调递增，因此可以考虑使用二分查找，来找到小于或等于`prefix[j] - target`的最大的`prefix[i]`，所求即为$(j - i)_{\min}$

## 代码
### 滑动窗口
```cpp
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int sum = 0;
        int min_len = nums.size() + 1;
        while (right < nums.size()) {
            while (sum < target && right < nums.size()) {
                sum += nums[right++];
            }
            while (sum >= target && left <= right) {
                if (sum >= target) {
                    min_len = min(min_len, right - left);
                }
                sum -= nums[left];
                left++; 

            }   
        }
        if (min_len > nums.size()) {
            return 0;
        }
        return min_len;
    }
};
```

### 前缀和+二分
```cpp
class Solution {
  public:
    int BSearch(int idx, int target, vector<int> &prefix) {
        int left = 0, right = idx;
        // 左闭右开
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefix[mid] < prefix[idx] - target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    int minSubArrayLen(int target, vector<int> &nums) {
        // 前缀和
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 1; i <= nums.size(); i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        // 二分查找
        int res = n + 1;
        for (int i = 1; i <= n; i++) {
            int j = BSearch(i, target - 1, prefix);
            if (prefix[i] >= target) {
                res = std::min(i - j + 1, res);
            }
        }
        if (res == n + 1) {
            return 0;
        }
        return res;
    }
};
```