暴力解法 - 超时 ```python class Solution: # 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 # 1 <= target <= 10e9 # 1 <= nums.length <= 10e5 # 1 <= nums[i] <= 10e4 # 子数组 是数组中连续的 非空 元素序列。 def minSubArrayLen(self, target: int, nums: List[int]) -> int: MAX = 100_000 ans = MAX s = 0 n = len( nums ) for i in range( n ): s = 0 for j in range( i, n ): s = s + nums[ j ] if s >= target: if ans > j - i + 1: ans = j - i + 1 break return 0 if ans == MAX else ans ``` --- **滑动窗口** **滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出想要的结果。** 在暴力解法中， - 一个for循环滑动窗口的起始位置， - 一个for循环为滑动窗口的终止位置， 用两个for循环 完成了一个不断搜索区间的过程。 现在：滑动窗口如何用一个for循环来完成这个操作？ ``` 如果用一个for循环，应该表示滑动窗口的起始位置，还是终止位置。 实现滑动窗口，主要确定如下三点： - 窗口内是什么？ - 如何移动窗口的起始位置？ - 如何移动窗口的结束位置？ 窗口就是满足 其和大于等于target 的长度最小的连续子数组。 窗口的起始位置如何移动：如果当前窗口的值大于等于target，窗口要向前移动了（即缩小窗口）。 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。 ``` **代码** ```python class Solution: # 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 # 1 <= target <= 10e9 # 1 <= nums.length <= 10e5 # 1 <= nums[i] <= 10e4 # 子数组 是数组中连续的 非空 元素序列。 def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len( nums ) ans = MAX = 100_010 # 滑动窗口内容:和大于等于target的长度最小的连续子数组。 w_len = 0 # 滑动窗口长度 w_sum = 0 # 滑动窗口总和 start = 0 for end in range( n ): w_sum += nums[ end ] # 调整滑动窗口的大小 并更新最小长度 while w_sum >= target: w_len = end - start + 1 if w_len < ans: ans = w_len w_sum -= nums[ start ] start += 1 # !important:变化窗口的起始位置 return 0 if ans == MAX else ans ``` 滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)降为O(n) **时间复杂度分析** ``` for里放一个while就以为是O(n^2)，其实不然： 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次， 每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。 ``` --- **滑动窗口模版** ``` start, end # 变化窗口终止位置 for end: # 根据窗口内容调整窗口起始位置 while( 判断条件 ): # 判断是否修改起始位置 judgeChangeStart() # 按要求返回值 return 结果值 ```