Python算法训练序列
双指针与滑动窗口 · Unit 07
← Unit 06
209
LeetCode 209Minimum Size Subarray Sum
窗口第一次满足条件，
只是收缩的开始。
寻找最短可行区间时，right负责把窗口和扩张到目标以上；一旦满足条件，就不断移动left，逐步剥离左端元素，并在每次仍然可行时更新更短答案。
LeetCode #209 原题内容中文转述 · 示例、约束与提交签名
题目要求
给定一个由正整数组成的数组 nums 和一个正整数 target，找出总和大于等于 target 的最短连续子数组长度。如果不存在这样的子数组，返回 0。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# 返回满足和不小于target的最短连续长度
约束
1 ≤ target ≤ 10⁹1 ≤ len(nums) ≤ 1000001 ≤ nums[i] ≤ 10000
示例
target = 7, nums = [2,3,1,2,4,3]
输出：2
最短子数组为[4,3]
输出：2
最短子数组为[4,3]
target = 4, nums = [1,4,4]
输出：1
输出：1
target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
输出：0
关键前提
数组元素全部为正数，因此right右移时窗口和不会减小，left右移时窗口和不会增大。这一单调性是滑动窗口成立的基础。
1. 区分最短目标
2. 体验重复枚举
3. 满足后持续收缩
4. 代码联动
5. 乘积窗口迁移
target = 7，nums = [2,3,1,2,4,3]等待操作
current_sum2
当前窗口长度1
历史最短 best∞
当前连续窗口 nums[left:right+1][2]
当前循环不变量
current_sum始终等于nums[left:right+1]的元素和。
当前移动规则
和不足时继续扩张；和达到target后，更新best并持续收缩，直到窗口重新不满足。
left0
right0
当前和2
是否满足否
最佳长度∞
从每个起点重新累加的重复工作
朴素方法从每个left重新向右求和，最坏需要O(n²)。由于元素全为正，旧窗口去掉左端后，其余元素和仍可直接复用，无需重新累计。
补全 LeetCode 提交代码最短可行窗口模板
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left =
current_sum = 0
best =
for right in range(len(nums)):
while :
best = min(best, )
current_sum -= nums[left]
left += 1
return
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
current_sum = 0
best = len(nums) + 1
for right in range(len(nums)):
current_sum += nums[right]
while current_sum >= target:
best = min(best, right - left + 1)
current_sum -= nums[left]
left += 1
return 0 if best == len(nums) + 1 else best
为什么必须是while？一个right位置可能对应多个满足条件的窗口。例如加入4后，[2,3,1,2,4]和[3,1,2,4]都满足target；只有持续收缩，才能找到该right下最短的可行窗口。
代码—窗口和—最短值联动轨迹：[2,3,1,2,4,3] / 7
1class Solution:
2 def minSubArrayLen(self, target: int, nums: List[int]) -> int:
3 left = 0
4 current_sum = 0
5 best = len(nums) + 1
6 for right in range(len(nums)):
7 current_sum += nums[right]
9 while current_sum >= target:
10 best = min(best, right - left + 1)
11 current_sum -= nums[left]
12 left += 1
14 return 0 if best == len(nums) + 1 else best
逐行播放，观察窗口第一次达到8后如何连续收缩，最终得到[4,3]长度2。
完成代码联动后进入乘积窗口迁移补全正确、查看答案或播放完整轨迹后解锁。
迁移题：LeetCode #713 乘积小于K的子数组
数组仍由正整数组成。right加入元素并更新乘积；当乘积大于等于k时持续除去左端。窗口合法后，以right结尾的合法子数组共有 right-left+1 个。
本单元形成的算法Skill
面对正数数组中的最短满足型连续区间，right负责扩大状态直到条件成立；条件成立后，必须用while持续移动left，并在每次收缩前更新答案。正数保证窗口和具有单调性，使已经移出的左端无需重新考虑。
LeetCode #209最短窗口正数单调性满足后收缩先更新再移除O(n)
#15锚点与去重
#3最长合法窗口
#438固定频次窗口
#209 当前满足后持续收缩
#76 下一单元频次缺口与最小覆盖