209。最小长度子数组题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/minimum-size-subarray-sum题目给定一个包含n个正整数和一个正整数s的数组，求最小的连续子数组length满足数组中sum≥s，返回其长度。如果没有符合条件的连续子??数组，则返回0。示例：输入：s=7,nums=[2,3,1,2,4,3]输出：2解释：子数组[4,3]是该条件下长度最小的连续子数组。进阶：如果你做过O(n)时间复杂度的解法，请尝试O(nlogn)时间复杂度的解法。解题思路：双指针/前缀+二分查找先看题目，题目说明给定数组nums的元素都是正整数，同时给定一个整数s，求子-数组和大于或等于s的最小连续子数组，并返回长度。如果不存在则返回0。先说特例吧。根据上题的意思，nums中的元素都是正整数。如果数组中所有元素的和小于s，那么子数组一定不满足要求，可以直接返回0。在高级提示的内容部分，要求先完成O(n)时间复杂度的求解。这就是我们现在要讲解的双指针思想的解决方案。具体实现思路：先定义双指针left和right，同时指向索引为0的初始位置；定义num_sum存储数组的总和，用于与s进行比较；先右移指针，维护更新num_sum的值，当num_sum满足大于等于s的条件时，先记录此时数组的长度，然后尝试减少数组的长度.这时候移动左指针，去掉左边的元素，重新判断num_sum和s的值。循环直到指针到达结束位置。用双指针实现思路的过程如下图所示：关于图中的参数，当num_sum大于等于s时，条件满足。s：题中给出的目标值num_sum：子数组的和left：左指针right：右指针ans：满足条件的子数组的长度见【代码实现#双指针】具体代码。以上就是双指针的思路了。下面尝试使用O(nlogn)复杂度的方法：前缀和+二分查找。关于前缀和，这里不解释这个概念。这里我们使用数组num_sum来存储nums的前缀和。num_sum[i]：表示从nums[0]到nums[i-1]的元素之和。还是因为【给定一个包含n个正整数的数组】的前提，那么我们存放前缀和的数组一定是升序排列的，这样也可以保证二分查找的正确性。我们得到存放前缀和的数组后，可以通过二分查找遍历数组得到一个索引index，使得num_sum[index]-num_sum[i-1]>=s，更新并维护子的长度数组，（此时的长度为索引-(i-1)），具体代码见【代码实现#前缀和+二分查找】。代码实现#双指针类解决方案：defminSubArrayLen(self,s:int,nums:List[int])->int:#先处理特殊情况，因为给定的数组都是正整数#如果所有元素的和在thearrayBotharelessthans#那么子数组的和一定小于s，直接返回0ifsum(nums)
