题目：
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, 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 <= 109 -
1 <= nums.length <= 105 -
1 <= nums[i] <= 104
思路如下：
解法一：滑动窗口
-
以右指针为准遍历，倘若区间内[left, right] (左闭右闭)的和未达到target，直接向右。
-
如果区间内的数大于等于target，则一步步缩小左边起始位置，即缩小窗口。直至区间内的数严格小于target
| 很重要，是 >=。因为我们会记录下等于时刻的长度。如果漏了可能会发现结果始终比答案多1，甚至错解
-
直至结束。
时间复杂度：O(n)
解法二：前缀和 + 二分搜索
时间复杂度：O(nlogn)
题解如下：
#解法一：滑动窗口
class Solution:def minSubArrayLen(self, target, nums):""":type: target: int, nums: List[int]:rtype: int"""left = 0ans = inf # 初始化为无穷大，便于后续取最小值s = 0 # 统计窗口内的和for right, x in enumerate(nums):s += x # 扩展右边界，累加元素值while s >= target: # 当窗口和满足条件时，尝试收缩左边界ans = min(ans,right-left+1)# 更新最小长度s -= nums[left] # 收缩左边界，减去左指针元素left += 1 # 左指针右移return ans if ans < inf else 0 # 处理不存在有效子数组的情况
#解法二：前缀和 + 二分搜索
class Solution:def minSubArrayLen(self, s, nums):""":type: target: int, nums: List[int]:rtype: int因为题目给出 1 <= nums[i] <= 105， 那么可以使用前缀和 加二分查找做1. 因为元素都大于0，所以前缀和肯定是递增的2. 我们以每一个元素为起始位置，二分找第一个大于 target的重点位置， 比较那个最小二分查找一次是 logn, 一共查找n次那么时间复杂度为 O(nlogn)"""n = len(nums)# 1. 计算前缀和, 初始长度为 n + 1, 方便计算. 任意 长度的和，均等于 prefix[i] - prefix[i - 1]prefix = [0] * (n + 1)for i in range(0, n):prefix[i + 1] = prefix[i] + nums[i]# 2. 定义二分查找方法def binarySreach(nums, start, target):"""1. 这里要理清楚， 假如 nums = 1 2 3 4， prefix是 0 1 3 6 10 长度是 n + 1.2. 依次遍历 nums， start 假如为1， 对应 nums的元素2， 前缀和prefix里对应的是 3， 下标为 2！ 计算nums里 2 + 3 + 4 的和， 对应到 prefix里是 prefix[n] - prefix[1], 所以搜索起来是从 start + 1开始到最后3. start对应 nums元素下标， start + 1 对应的是 prefix中， 此元素的前缀和。"""left = start + 1# 这里的nums 是 prefixright = len(nums) - 1while left < right:middle = (left + right) // 2 if nums[middle] - nums[start] >= target:right = middleelse:left = middle + 1# 看最后一个位置 是否符合，有可能小于return left - start if nums[left] - nums[start] >= target else n + 1# 3. 寻找满足条件长度最小子数组minLength = n + 1# 使 nums 前n个元素都作为开始元素， 计算第一个 大于 target的子数组长for i in range(n):length = binarySreach(prefix, i, s)minLength = min(minLength, length)return minLength if minLength != n + 1 else 0
#使用python的标准库
class Solution:def minSubArrayLen(self, target, nums):""":type: target: int, nums: List[int]:rtype: int"""n = len(nums)prefix = [0] * (n + 1)for i in range(n):prefix[i + 1] = prefix[i] + nums[i]min_length = n + 1for i in range(n):# 在 prefix[i+1..n] 中查找第一个 >= prefix[i] + target 的位置j = bisect_left(prefix, prefix[i] + target, i + 1, n + 1)if j <= n:min_length = min(min_length, j - i)return min_length if min_length <= n else 0bisect_left(prefix, prefix[i] + target, i+1, n+1)：
在 prefix 中从位置 i+1 到 n+1 查找第一个 >= prefix[i] + target 的位置。
