Minimum Size Subarray Sum：从 O(n²) 暴力到 O(n) 滑动窗口，我只改了 4 行

读完本文你将了解：滑动窗口的本质不是一行模板，而是对「最优子结构」的直觉 | AI 是怎么一步步从暴力解里挖出滑动窗口的 | 这道题在 Uber 动态定价系统里的真实映射

📋 题目

原题：给定一个正整数数组nums和一个正整数target，求出数组中和至少为 target 的最短连续子数组的长度。如果不存在这样的子数组，返回 0。

最优解是 [4,3]，长度 2。

💡 先问一个问题

如果让 ChatGPT 第一眼看这道题，它会怎么写？

它几乎必然会先用双重循环暴力遍历。

这不是 AI 笨——暴力解对应的是人类的直觉：枚举所有连续子数组，算和，选最短的。AI 的弱点也是人类的弱点：直觉往往是慢解法。

但 AI 有个好处：它会把每一步推理都摊开来。你能看到它从哪一步开始怀疑暴力解不够好，然后怎么找到更优方案。

🤖 第一版：暴力解，直觉的代价

最朴素的想法：两层循环枚举所有连续子数组：

defminSubArrayLen_brute(target,nums):n=len(nums)ans=n+1foriinrange(n):total=0forjinrange(i,n):total+=nums[j]iftotal>=target:ans=min(ans,j-i+1)breakreturnansifans<=nelse0

时间复杂度 O(n²)，空间 O(1)。

AI 的直觉没错。但它枚举完 [2,3,1,2] 之后，下一轮从 [3,1,2,4] 开始——中间有大量重复计算。nums[1]+nums[2]+nums[3] 这个和，第一轮算过，第二轮又在算。

它会什么时候意识到这个问题？通常是在它自己测试一个长度为 10⁵ 的数组，然后卡住的时候。

🧠 滑动窗口：让指针「滑」起来

核心直觉就一句话：

数组全是正数，右指针右移让和变大，左指针右移让和变小。我们只需要找到「刚好 ≥ target」的那个时刻。

算法流程：

1. 右指针r向右滑，累加total
2. 一旦total ≥ target，尝试把左指针l往右移（缩小窗口），同时更新最短长度
3. 重复直到r走到头

defminSubArrayLen(target,nums):l=total=0ans=len(nums)+1forrinrange(len(nums)):total+=nums[r]whiletotal-nums[l]>=target:total-=nums[l]l+=1iftotal>=target:ans=min(ans,r-l+1)returnansifans<=len(nums)else0

为什么是 O(n)？左指针l和右指针r都只向右移动，每个元素最多被访问两次（一次r加进来，一次l移出去）。没有回头，没有重复计算。

窗口的「呼吸」节奏：

☕ Java 实现

CSDN 用户里 Java 开发者最多，同样的思路，Java 版本：

publicintminSubArrayLen(inttarget,int[]nums){intl=0,total=0,ans=nums.length+1;for(intr=0;r<nums.length;r++){total+=nums[r];while(total-nums[l]>=target){total-=nums[l];l++;}if(total>=target){ans=Math.min(ans,r-l+1);}}returnans<=nums.length?ans:0;}

Python 和 Java 的唯一区别是 Java 没有 break，逻辑完全一致。

🔍 滑动窗口模式拆解

什么时候用滑动窗口？

三个条件同时满足：

如果三个条件都满足，滑动窗口大概率能用。如果第三条不满足（比如要找和等于某个值，且数组有负数），那就不是滑动窗口的问题了。

同类题：

• LeetCode 3：无重复字符的最长字符串（滑动窗口 + 哈希表）
• LeetCode 76：最小覆盖子串
• LeetCode 340：至多包含 K 个不同字符的最长子串

🏗️ 真实产品场景：Uber 动态定价中的时间窗口

这道题在 Uber 的定价系统里有直接的映射。

Uber 的时间窗口定价问题：每个 5 分钟时间片都有供需数据。当某个时段的供需比达到阈值，系统要找出满足该阈值的最短连续时间区间。

这和minSubArrayLen完全一致：正整数数组 = 供需比数据，target = 定价阈值，最短连续子数组 = 最短需要进入动态定价的时间区间。

Uber 2016 年的论文明确提到了用滑动窗口做时间序列的局部统计。这道题不是抽象的脑筋急转弯——它是 Uber 面试里用来验证候选人能不能把产品问题翻译成算法问题的经典题。

✅ 面试官的点评

写到什么程度算通过？

• 通过线：能写出来 O(n) 的滑动窗口实现
• 加分项：
  • 能说出为什么双指针不会漏解（因为左指针只向右，不会跳过解）
  • 能处理全 0 或者全小于 target 的边界情况
  • 能指出 nums 包含负数时滑动窗口不再适用
• 常见踩坑：
  • while循环的条件写反（写成total < target而不是total - nums[l] >= target）
  • ans的初始值设成 0，然后漏了无解的情况
  • 窗口缩小时没更新total

📊 同类题推荐

来源说明：

• ✅ 已验证：LeetCode 官方题解 + 本地 Python/Java 双语言实测
• 📄 文档/论文：Uber Dynamic Pricing 论文 (2016)