 暴力到 O(n) 滑动窗口，我只改了 4 行)
读完本文你将了解滑动窗口的本质不是一行模板而是对「最优子结构」的直觉 | AI 是怎么一步步从暴力解里挖出滑动窗口的 | 这道题在 Uber 动态定价系统里的真实映射 题目原题给定一个正整数数组nums和一个正整数target求出数组中和至少为 target 的最短连续子数组的长度。如果不存在这样的子数组返回 0。项目说明输入target 7, nums [2,3,1,2,4,3]输出2约束1 ≤ target ≤ 10⁹1 ≤ nums.length ≤ 10⁵1 ≤ nums[i] ≤ 10⁵最优解是 [4,3]长度 2。 先问一个问题如果让 ChatGPT 第一眼看这道题它会怎么写它几乎必然会先用双重循环暴力遍历。这不是 AI 笨——暴力解对应的是人类的直觉枚举所有连续子数组算和选最短的。AI 的弱点也是人类的弱点直觉往往是慢解法。但 AI 有个好处它会把每一步推理都摊开来。你能看到它从哪一步开始怀疑暴力解不够好然后怎么找到更优方案。 第一版暴力解直觉的代价最朴素的想法两层循环枚举所有连续子数组defminSubArrayLen_brute(target,nums):nlen(nums)ansn1foriinrange(n):total0forjinrange(i,n):totalnums[j]iftotaltarget:ansmin(ans,j-i1)breakreturnansifansnelse0时间复杂度 O(n²)空间 O(1)。AI 的直觉没错。但它枚举完 [2,3,1,2] 之后下一轮从 [3,1,2,4] 开始——中间有大量重复计算。nums[1]nums[2]nums[3] 这个和第一轮算过第二轮又在算。它会什么时候意识到这个问题通常是在它自己测试一个长度为 10⁵ 的数组然后卡住的时候。暴力枚举O(n²)发现重复计算subarray sum 被反复加能不能复用右指针往右走时,左指针也右移?滑动窗口O(n) 滑动窗口让指针「滑」起来核心直觉就一句话数组全是正数右指针右移让和变大左指针右移让和变小。我们只需要找到「刚好 ≥ target」的那个时刻。算法流程右指针r向右滑累加total一旦total ≥ target尝试把左指针l往右移缩小窗口同时更新最短长度重复直到r走到头defminSubArrayLen(target,nums):ltotal0anslen(nums)1forrinrange(len(nums)):totalnums[r]whiletotal-nums[l]target:total-nums[l]l1iftotaltarget:ansmin(ans,r-l1)returnansifanslen(nums)else0为什么是 O(n)左指针l和右指针r都只向右移动每个元素最多被访问两次一次r加进来一次l移出去。没有回头没有重复计算。窗口的「呼吸」节奏渲染错误:Mermaid 渲染失败: Parse error on line 7: ...U V --|否|r继续右移| R U -- W[更新最 ----------------------^ Expecting SEMI, NEWLINE, SPACE, EOF, SQS, SHAPE_DATA, AMP, STYLE_SEPARATOR, DOUBLECIRCLESTART, PS, (-, STADIUMSTART, SUBROUTINESTART, VERTEX_WITH_PROPS_START, COLON, CYLINDERSTART, DIAMOND_START, TAGEND, TRAPSTART, INVTRAPSTART, START_LINK, LINK, LINK_ID, DOWN, DEFAULT, NUM, COMMA, NODE_STRING, BRKT, MINUS, MULT, UNICODE_TEXT, got PIPE☕ Java 实现CSDN 用户里 Java 开发者最多同样的思路Java 版本publicintminSubArrayLen(inttarget,int[]nums){intl0,total0,ansnums.length1;for(intr0;rnums.length;r){totalnums[r];while(total-nums[l]target){total-nums[l];l;}if(totaltarget){ansMath.min(ans,r-l1);}}returnansnums.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] targetans的初始值设成 0然后漏了无解的情况窗口缩小时没更新total 同类题推荐题目难度一句话思路LC 3 无重复字符的最长字符串Medium滑动窗口 哈希表记录字符位置LC 76 最小覆盖子串Hard滑动窗口 频次计数LC 340 至多 K 个不同字符Medium滑动窗口 哈希表计数来源说明✅ 已验证LeetCode 官方题解 本地 Python/Java 双语言实测 文档/论文Uber Dynamic Pricing 论文 (2016)
读完本文你将了解滑动窗口的本质不是一行模板而是对「最优子结构」的直觉 | AI 是怎么一步步从暴力解里挖出滑动窗口的 | 这道题在 Uber 动态定价系统里的真实映射 题目原题给定一个正整数数组nums和一个正整数target求出数组中和至少为 target 的最短连续子数组的长度。如果不存在这样的子数组返回 0。项目说明输入target 7, nums [2,3,1,2,4,3]输出2约束1 ≤ target ≤ 10⁹1 ≤ nums.length ≤ 10⁵1 ≤ nums[i] ≤ 10⁵最优解是 [4,3]长度 2。 先问一个问题如果让 ChatGPT 第一眼看这道题它会怎么写它几乎必然会先用双重循环暴力遍历。这不是 AI 笨——暴力解对应的是人类的直觉枚举所有连续子数组算和选最短的。AI 的弱点也是人类的弱点直觉往往是慢解法。但 AI 有个好处它会把每一步推理都摊开来。你能看到它从哪一步开始怀疑暴力解不够好然后怎么找到更优方案。 第一版暴力解直觉的代价最朴素的想法两层循环枚举所有连续子数组defminSubArrayLen_brute(target,nums):nlen(nums)ansn1foriinrange(n):total0forjinrange(i,n):totalnums[j]iftotaltarget:ansmin(ans,j-i1)breakreturnansifansnelse0时间复杂度 O(n²)空间 O(1)。AI 的直觉没错。但它枚举完 [2,3,1,2] 之后下一轮从 [3,1,2,4] 开始——中间有大量重复计算。nums[1]nums[2]nums[3] 这个和第一轮算过第二轮又在算。它会什么时候意识到这个问题通常是在它自己测试一个长度为 10⁵ 的数组然后卡住的时候。暴力枚举O(n²)发现重复计算subarray sum 被反复加能不能复用右指针往右走时,左指针也右移?滑动窗口O(n) 滑动窗口让指针「滑」起来核心直觉就一句话数组全是正数右指针右移让和变大左指针右移让和变小。我们只需要找到「刚好 ≥ target」的那个时刻。算法流程右指针r向右滑累加total一旦total ≥ target尝试把左指针l往右移缩小窗口同时更新最短长度重复直到r走到头defminSubArrayLen(target,nums):ltotal0anslen(nums)1forrinrange(len(nums)):totalnums[r]whiletotal-nums[l]target:total-nums[l]l1iftotaltarget:ansmin(ans,r-l1)returnansifanslen(nums)else0为什么是 O(n)左指针l和右指针r都只向右移动每个元素最多被访问两次一次r加进来一次l移出去。没有回头没有重复计算。窗口的「呼吸」节奏渲染错误:Mermaid 渲染失败: Parse error on line 7: ...U V --|否|r继续右移| R U -- W[更新最 ----------------------^ Expecting SEMI, NEWLINE, SPACE, EOF, SQS, SHAPE_DATA, AMP, STYLE_SEPARATOR, DOUBLECIRCLESTART, PS, (-, STADIUMSTART, SUBROUTINESTART, VERTEX_WITH_PROPS_START, COLON, CYLINDERSTART, DIAMOND_START, TAGEND, TRAPSTART, INVTRAPSTART, START_LINK, LINK, LINK_ID, DOWN, DEFAULT, NUM, COMMA, NODE_STRING, BRKT, MINUS, MULT, UNICODE_TEXT, got PIPE☕ Java 实现CSDN 用户里 Java 开发者最多同样的思路Java 版本publicintminSubArrayLen(inttarget,int[]nums){intl0,total0,ansnums.length1;for(intr0;rnums.length;r){totalnums[r];while(total-nums[l]target){total-nums[l];l;}if(totaltarget){ansMath.min(ans,r-l1);}}returnansnums.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] targetans的初始值设成 0然后漏了无解的情况窗口缩小时没更新total 同类题推荐题目难度一句话思路LC 3 无重复字符的最长字符串Medium滑动窗口 哈希表记录字符位置LC 76 最小覆盖子串Hard滑动窗口 频次计数LC 340 至多 K 个不同字符Medium滑动窗口 哈希表计数来源说明✅ 已验证LeetCode 官方题解 本地 Python/Java 双语言实测 文档/论文Uber Dynamic Pricing 论文 (2016)
