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) ≤ 100000
  • 1 ≤ nums[i] ≤ 10000

示例

target = 7, nums = [2,3,1,2,4,3]
输出：2
最短子数组为[4,3]
target = 4, nums = [1,4,4]
输出：1
target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

关键前提

数组元素全部为正数，因此right右移时窗口和不会减小，left右移时窗口和不会增大。这一单调性是滑动窗口成立的基础。

先连接上一单元：窗口不只维护字符，也可以维护数值状态Unit 06 → Unit 07
#438：固定长度窗口

窗口长度由 len(p) 决定；每轮更新进入和离开的字符频次，判断组成是否匹配。

→
#209：可变长度窗口

窗口长度由 current_sum 是否达到 target 决定；right 负责达到条件，left 负责继续压缩长度。

共同骨架：窗口表示一段连续区间，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 的子数组

先完整认识新题，再判断 #209 的窗口骨架还能复用多少。读题检查完成前，不进入批量计数公式和代码迁移。

1. 认识 #713 原题
2. 对照最短窗口与计数窗口
3. 映射四个语义变化
4. 拼装并运行官方样例
题目内容、示例与约束依据 LeetCode 官方题面整理查看官方原题 ↗
713. 乘积小于 K 的子数组Medium · Array · Sliding Window · Prefix Sum · Binary Search

题目要求

给定整数数组 nums 和整数 k，返回所有元素乘积严格小于 k 的非空连续子数组数量。

class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: # 返回满足乘积严格小于 k 的连续子数组总数

约束

  • 1 ≤ len(nums) ≤ 3 × 10⁴
  • 1 ≤ nums[i] ≤ 1000
  • 0 ≤ k ≤ 10⁶

官方示例

nums = [10,5,2,6], k = 100
输出：8
合法子数组：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]
nums = [1,2,3], k = 0
输出：0

严格不等号

[10,5,2] 的乘积等于100，因此不合法；必须满足乘积 < k，而不是 ≤ k。

连续且非空统计的是数组中的连续区间，不能跳过中间元素，也不包含空数组。
严格小于乘积等于 k 仍然不合法，收缩条件应为 product ≥ k。
返回数量答案是所有合法子数组的总数，不是长度、下标或某个具体窗口。
正整数条件所有因子至少为1；因此 k ≤ 1 时不存在乘积严格小于 k 的非空子数组。

读题检查 1｜函数最终返回什么？

读题检查 2｜为什么 [10,5,2] 不计入，而 [5,2,6] 可以计入？

已经掌握：#209 长度最小的子数组

窗口状态：current_sum 条件：current_sum ≥ target 时窗口可行 目标：维护最短长度 best 收缩时机：可行后继续收缩 答案更新：每次收缩前更新 best

准备迁移：#713 乘积小于 K 的子数组

窗口状态：product 条件：product < k 时窗口合法 目标：累计全部合法子数组数量 收缩时机：product ≥ k 时恢复合法 答案更新：窗口合法后批量增加 right-left+1
保持不变元素全为正数；right 扩张窗口，left 只向右收缩；窗口状态都能通过进入和离开元素增量维护。
状态变化把加法和改为乘积；移除左端时从减法改为除法。
目标变化#209 求一个最短长度；#713 要统计所有合法区间，因此答案从 min 更新变成批量计数。
为什么合法后可以一次增加 right-left+1？ 收缩结束后，[left,right] 的乘积小于 k。固定右端 right，起点取 left、left+1、…、right 时，只会继续移除至少为1的正因子，乘积不会变大，因此这 right-left+1 个后缀子数组全部合法。

下面哪句话最准确地描述了迁移幅度？

槽位 A｜为什么要先处理 k ≤ 1？

槽位 B｜right 加入新元素时怎样更新窗口状态？

槽位 C｜乘积不合法时怎样持续收缩？

槽位 D｜窗口恢复合法后怎样统计并返回？

更新顺序与 #209 相反：#209 在“条件成立”时先记录长度再收缩；#713 在“条件不成立”时先收缩，恢复合法后再批量计数。
复用的边界骨架left=0，right 逐项向右；窗口不满足要求时使用 while 推进 left。
替换的状态运算current_sum += / -= 替换为 product *= / //=。
新增的批量证明固定 right 后，合法窗口的所有后缀都合法，一次增加 right-left+1。

#209：求最短可行长度

left = 0
current_sum = 0
best = n + 1
for right in range(n):
    current_sum += nums[right]
    while current_sum >= target:
        best = min(best, right-left+1)
        current_sum -= nums[left]
        left += 1
return best / 0

#713：统计全部合法子数组

if k <= 1: return 0
left = 0
product = 1
answer = 0
for right in range(n):
    product *= nums[right]
    while product >= k:
        product //= nums[left]
        left += 1
    answer += right-left+1
return answer
官方样例运行轨迹0/0
可选挑战：脱离槽位，独立重写完整代码

这一步不阻碍主流程。先完整运行官方样例，再凭“乘入—超限时除去—合法后批量计数”重写。

本单元形成的算法Skill

面对正数数组中的最短满足型连续区间，right负责扩大状态直到条件成立；条件成立后，必须用while持续移动left，并在每次收缩前更新答案。正数保证窗口和具有单调性，使已经移出的左端无需重新考虑。

LeetCode #209最短窗口正数单调性满足后收缩先更新再移除O(n)
#15锚点与去重
#3最长合法窗口
#438固定频次窗口
#209 当前满足后持续收缩
#76 下一单元频次缺口与最小覆盖