【学习记录】滑动窗口五题通关从食堂打饭到上下文窗口——算法与大模型的内存管理哲学在经历了“两数之和”的哈希表思维和“跳跃游戏”的贪心思维之后我们来到了算法面试中另一个举足轻重的专题——滑动窗口Sliding Window。如果说哈希表是“空间换时间”的典范贪心是“局部最优→全局最优”的策略那么滑动窗口就是“双指针协同移动”的极致艺术。今天我们用“食堂打饭窗口”的比喻把五道经典的滑动窗口题目串在一起讲透——从最基础的子数组求和到需要哈希表辅助的最小覆盖子串再到固定长度的异位词检测。读完这篇你会对滑动窗口产生肌肉记忆。 目录滑动窗口核心思想食堂打饭的比喻题目一长度最小的子数组LeetCode 209题目二水果成篮LeetCode 904题目三找到字符串中所有字母异位词LeetCode 438题目四字符串的排列LeetCode 567题目五最小覆盖子串LeetCode 76滑动窗口全题型总结AI知识扩展滑动窗口与大模型上下文管理留给你的思考题一、滑动窗口核心思想食堂打饭的比喻想象你在学校食堂排队打饭。窗口[left, right]里的菜必须满足某种条件——比如“荤素搭配”无重复字符或“总价不超过预算”和 ≥ target。你的目标是找到满足条件的最长/最短窗口。滑动窗口的本质right指针不断向右扩展“打更多的菜”。当窗口不满足条件时left指针向右收缩“扔掉一些菜”。在这个过程中你记录下所有满足条件的窗口取最优值。三类滑动窗口类型代表题目核心特征不定长求最小209. 长度最小的子数组满足条件时收缩左边界不定长求最大904. 水果成篮不满足条件时收缩左边界固定长度438. 异位词 / 567. 排列窗口大小固定滑动比较带哈希表验证76. 最小覆盖子串需要计数验证窗口是否满足复杂条件二、题目一长度最小的子数组LeetCode 209题目描述给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和≥ target的长度最小的连续子数组并返回其长度。如果不存在返回0。示例输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是长度最小的满足条件的子数组。从熟悉到陌生自助餐的比喻你在吃自助餐目标是吃到至少 7 分饱总和 ≥ target但你想用最少的食物量达到这个目标。你不断往盘子里夹菜right右移直到感觉吃饱了和 ≥ target。然后开始往外扔菜left左移直到刚好吃饱为止——此时记录窗口长度。继续夹新菜重复这个过程。代码实现defminSubArrayLen(target,nums):left0total0min_lenfloat(inf)forrightinrange(len(nums)):totalnums[right]# 右指针扩张whiletotaltarget:# 满足条件尝试收缩min_lenmin(min_len,right-left1)total-nums[left]left1returnmin_lenifmin_len!float(inf)else0核心要点要素说明窗口条件窗口和 ≥ target收缩时机满足条件时立即收缩求最小更新答案每次满足条件时更新min_len复杂度O(n)每个元素进出窗口各一次三、题目二水果成篮LeetCode 904题目描述你正在探访一个农场农场有一排果树用整数数组fruits表示fruits[i]是第i棵树上的水果种类。你有两个篮子每个篮子只能装一种水果。求最多能采摘多少棵树的果实必须连续采摘且最多两种类型。示例输入fruits [1,2,3,2,2] 输出4 解释可以采摘 [2,3,2,2] 这四棵树共两种水果2和3。从熟悉到陌生水果摊的比喻你有一个只能装两种水果的篮子最多两种类型。你沿着水果摊走想尽可能多地往篮子里装水果但一旦出现第三种水果你就必须从左边扔掉一些水果直到篮子里只剩两种类型。代码实现deftotalFruit(fruits):left0max_len0count{}# 记录窗口内每种水果的数量forright,fruitinenumerate(fruits):count[fruit]count.get(fruit,0)1whilelen(count)2:# 超过两种水果收缩窗口count[fruits[left]]-1ifcount[fruits[left]]0:delcount[fruits[left]]left1max_lenmax(max_len,right-left1)returnmax_len核心要点要素说明窗口条件窗口中水果种类 ≤ 2收缩时机种类 2 时收缩求最大更新答案每次收缩后更新max_len复杂度O(n)哈希表维护种类计数四、题目三找到字符串中所有字母异位词LeetCode 438题目描述给定两个字符串s和p找到s中所有p的异位词子串返回这些子串的起始索引。示例输入s cbaebabacd, p abc 输出[0, 6] 解释索引0的子串 cba 是 abc 的异位词索引6的子串 bac 也是。从熟悉到陌生固定长度的比喻你有一个固定大小的模板p的长度在长字符串s上滑动每次检查窗口内的字符频率是否和模板完全一致。这是一个固定窗口 计数比较的问题。代码实现deffindAnagrams(s,p):fromcollectionsimportCounter needCounter(p)windowCounter()res[]left0forrightinrange(len(s)):window[s[right]]1ifright-left1len(p):# 窗口过大左移window[s[left]]-1ifwindow[s[left]]0:delwindow[s[left]]left1ifwindowneed:res.append(left)returnres核心要点要素说明窗口大小固定为len(p)窗口条件window need收缩时机窗口大小超过len(p)时左移复杂度O(n)每次移动更新计数器五、题目四字符串的排列LeetCode 567题目描述给定两个字符串s1和s2判断s2是否包含s1的排列即s1的某个排列是s2的子串。示例输入s1 ab, s2 eidbaooo 输出true 解释s2 包含 baab 的排列之一与 438 的本质关系这道题和 438 本质上完全一样——只是返回值从“所有起始索引”变成了“是否存在”。把 438 的代码稍作修改即可。代码实现defcheckInclusion(s1,s2):fromcollectionsimportCounter needCounter(s1)windowCounter()left0forrightinrange(len(s2)):window[s2[right]]1ifright-left1len(s1):window[s2[left]]-1ifwindow[s2[left]]0:delwindow[s2[left]]left1ifwindowneed:returnTruereturnFalse六、题目五最小覆盖子串LeetCode 76题目描述给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果不存在返回空字符串。示例输入s ADOBECODEBANC, t ABC 输出BANC从熟悉到陌生拼图的比喻你需要用s中的字符片段拼出一个包含t中所有字符且数量足够的完整图案。你要找到最短的这样的片段。这是滑动窗口中最复杂的一道需要哈希表记录t中每个字符的需求量。维护valid变量记录已满足的字符种类数。当valid len(need)时尝试收缩左边界。代码实现defminWindow(s,t):fromcollectionsimportdefaultdict needdefaultdict(int)forchint:need[ch]1windowdefaultdict(int)left0valid0start0min_lenfloat(inf)forright,chinenumerate(s):# 右移窗口ifchinneed:window[ch]1ifwindow[ch]need[ch]:valid1# 当所有字符都满足时尝试收缩左边界whilevalidlen(need):ifright-left1min_len:min_lenright-left1startleft ds[left]left1ifdinneed:ifwindow[d]need[d]:valid-1window[d]-1returnifmin_lenfloat(inf)elses[start:startmin_len]核心要点要素说明窗口条件窗口内包含t的所有字符数量足够验证机制valid记录已满足的字符种类数收缩时机满足条件时收缩求最小复杂度O(n)哈希表维护字符计数难点同时维护valid和字符计数七、滑动窗口全题型总结题目窗口类型条件收缩时机更新答案209. 长度最小子数组不定长和 ≥ target满足时收缩每次收缩后904. 水果成篮不定长种类 ≤ 2不满足时收缩每次收缩后438. 异位词固定长度window need窗口超长时左移每次匹配567. 排列固定长度window need窗口超长时左移发现即返回76. 最小覆盖不定长valid len(need)满足时收缩每次收缩后核心模式模板left0# 初始化数据结构forrightinrange(len(s)):# 1. 右移窗口加入 s[right]# 2. 更新窗口状态# 3. 判断是否需要收缩左边界whilecondition:# 不满足/满足条件# 更新答案# 左移窗口移除 s[left]left1八、AI知识扩展滑动窗口与大模型上下文管理8.1 上下文窗口大模型的“滑动窗口”在 Transformer 大模型中上下文窗口Context Window是决定模型“记忆长度”的核心参数。模型只能“看到”固定长度内的历史 token这与滑动窗口的思想高度一致滑动窗口算法题大模型上下文窗口right指针不断扩张新 token 不断加入生成序列left指针收缩丢弃旧元素窗口满时丢弃最老的 token窗口内维护“合法条件”窗口内维护“注意力范围”最小/最大窗口长度上下文窗口固定长度8.2 RAG 中的 Top-K 检索在 RAG 系统中我们通常检索 Top‑K 个相关文档片段然后拼接到 Prompt 中。这个 Top‑K 本质上也是一个固定长度的滑动窗口——它从向量数据库中“截取”最相关的 K 个片段形成模型的“即时上下文”。8.3 从“滑动窗口”到“注意力稀疏化”当上下文窗口极大时如 128K 或 1M模型需要处理 O(n²) 的注意力计算。为了解决这个问题研究人员开发了滑动窗口注意力Sliding Window Attention——每个 token 只关注其附近的 W 个 token而不是全部历史。这和算法中的滑动窗口思想如出一辙用局部信息替代全局信息从而将时间复杂度从 O(n²) 降为 O(n×W)。九、留给你的思考题问题如果s的长度是 10⁶t的长度是 100minWindow的时间复杂度是 O(n)空间复杂度 O(Σ)。你能解释为什么它比暴力枚举所有子串O(n³)快这么多吗提示暴力枚举所有子串需要 O(n²) 个子串每个子串检查需要 O(n) 时间。而滑动窗口只让左右指针各遍历一次且每次更新都是 O(1) 的哈希表操作。连接到大模型在大模型的注意力机制中为什么我们要用“滑动窗口注意力”来替代全局注意力——因为序列越长全局注意力的计算量增长越快O(n²)而滑动窗口注意力将每个 token 的关注范围限制在局部将复杂度降为 O(n×W)。这和“子串枚举”与“滑动窗口”的关系惊人地相似——剪枝掉的不是答案而是那些注定不是最优的搜索空间。