 不是运气，是两条指针各走一遍)
一句话理解滑动窗口 两个指针圈出一段合法区间。右指针只管往前跑左指针在后面追——像截视频时拖那个选区框你只关心框里的东西。 本文产出滑动窗口模式的通用代码模板可直接复制3 道由浅入深的经典面试题 完整解题思路2 个真实产品场景Netflix trending topics / 广告投放频控面试官视角的评分要点❓ 这个模式解决什么问题一句话定义给定一个序列数组/字符串找一个满足某种约束条件的连续子序列时用滑动窗口在 O(n) 时间内解决。核心洞见暴力法把每个子数组从头算一遍O(n²)。但如果你只盯着当前窗口每次滑动时只做增量更新——加一个、减一个——那就降到 O(n) 了。不适用的情况别看到子数组就无脑套滑动窗口。下面这三种情况套了反而更麻烦❌ 不适合原因该用什么要求子序列但不要求连续窗口要求连续性动态规划 / 双指针数组中有负数固定目标和的场景右移不一定增大窗口和前缀和 HashMap需要精确匹配某个最小值/最大值的子数组数约束不满足向右扩张时单调前缀和 计数简单口诀有负数别用滑动窗口求目标和除非是变体非连续子序列别用滑动窗口。 模式识别什么样的题用滑动窗口特征说明示例题要求连续子数组/子串题目明确说连续或subarray最长无重复子串存在单调性右边界扩张后不满足条件时只能收缩左边界和 ≥ target 的最短子数组需要最优值min/max 某个窗口属性滑动窗口最大值窗口状态可增量更新加一个元素、删一个元素时O(1) 更新状态字符频率计数固定窗口 vs 可变窗口固定窗口窗口大小 k 是给定的 → for 循环套一个 if 条件 可变窗口窗口大小不固定 → while 循环收缩左边界判断方法看题目是否给了固定窗口大小 k。给了 → 固定窗口模板没给 → 可变窗口模板。 代码模板模板 A固定窗口deffixed_sliding_window(arr,k): 固定大小窗口模板 适用场景窗口大小 k 已知求窗口内某属性的最大/最小值 window_sum0best0forrightinrange(len(arr)):# 1. 扩张加入右边新元素window_sumarr[right]# 2. 判断窗口是否形成前 k-1 次循环先积累不判断ifrightk-1:continue# 3. 窗口形成更新答案bestmax(best,window_sum)# 4. 收缩移除左边过期元素准备下一次滑动leftright-k1window_sum-arr[left]returnbest模板 B可变窗口defvariable_sliding_window(s): 可变大小窗口模板 适用场景寻找满足某条件的最短/最长子串 fromcollectionsimportCounter windowCounter()# 或 set / dict取决于需要什么状态left0best0forrightinrange(len(s)):# 1. 扩张加入右边新元素window[s[right]]1# 2. 收缩当条件不满足时持续移动左边界直到恢复合法whilenotis_valid(window):# 条件因题而异window[s[left]]-1ifwindow[s[left]]0:delwindow[s[left]]left1# 3. 此时窗口内状态合法更新答案bestmax(best,right-left1)returnbest记忆口诀“右边进左边出合法时才记录”// Java 版 可变窗口模板publicintvariableWindow(Strings){MapCharacter,IntegerwindownewHashMap();intleft0,best0;for(intright0;rights.length();right){// 扩张charcs.charAt(right);window.merge(c,1,Integer::sum);// 收缩while(!isValid(window)){chards.charAt(left);window.merge(d,-1,Integer::sum);if(window.get(d)0)window.remove(d);left;}// 合法状态更新答案bestMath.max(best,right-left1);}returnbest;}️ 核心原理滑动窗口的本质增量更新 双指针协调是否右指针 right不断扩张窗口状态变化O(1) 增量更新窗口合法?更新最优解左指针 left 追赶恢复合法性right 继续前进为什么暴力法是 O(n²) 而不是 O(n)暴力法的问题在于每次窗口变化都重新计算状态滑动窗口 O(n)暴力法 O(n²)滑动窗口 O(n)暴力法 O(n²)枚举所有子数组 (i,j)指针协调各走 O(n)i0, j0..n-1 遍历 O(n)i1, j1..n-1 遍历 O(n-1)...共 O(n²) 次right 从 0 走到 n-1n 步left 从 0 最多走到 n-1n 步总计 2n O(n)关键差异暴力法每次重新计算滑动窗口复用上一次的结果只做增量修改。 三题进阶第 1 题MediumLongest Substring Without Repeating Characters原题给定字符串 s找出不含重复字符的最长子串的长度。项目内容输入s “abcabcbb”输出3“abc” 或 “bca” 或 “cab”约束0 ≤ s.length ≤ 5×10⁴字符集为 ASCII解题思路维护一个set记录当前窗口内的字符right扩张如果新字符已在 set 中说明出现重复left追赶从 set 中移除字符直到重复字符被踢出每次窗口合法时更新最长长度deflengthOfLongestSubstring(s:str)-int:seenset()left0best0forright,chinenumerate(s):whilechinseen:# 出现重复收缩seen.remove(s[left])left1seen.add(ch)# 加入新字符bestmax(best,right-left1)returnbestpublicintlengthOfLongestSubstring(Strings){SetCharacterseennewHashSet();intleft0,best0;for(intright0;rights.length();right){charcs.charAt(right);while(seen.contains(c)){seen.remove(s.charAt(left));left;}seen.add(c);bestMath.max(best,right-left1);}returnbest;}时间复杂度 O(n)空间 O(min(n, 字符集大小))。第 2 题MediumMinimum Size Subarray Sum原题给定正整数数组 nums 和目标值 target找出和 ≥ target 的最短连续子数组长度。项目内容输入target 7, nums [2,3,1,2,4,3]输出2子数组 [4,3] 的和 7约束1 ≤ target ≤ 10⁹1 ≤ nums.length ≤ 10⁵为什么可以用滑动窗口数组元素全是正整数 → 窗口扩张时和一定增大收缩时和一定减小。单调性成立。defminSubArrayLen(target:int,nums:list[int])-int:left0window_sum0bestfloat(inf)forrightinrange(len(nums)):window_sumnums[right]# 扩张whilewindow_sumtarget:# 满足条件尝试收缩bestmin(best,right-left1)window_sum-nums[left]left1returnbestifbest!float(inf)else0陷阱提示如果 nums 中有负数如 [-1, 2, 3]不能直接用滑动窗口——扩张不一定增加和收缩不一定减少和。此时要用前缀和。第 3 题HardSliding Window Maximum原题给定数组 nums 和窗口大小 k返回每个窗口中最大值的数组。项目内容输入nums [1,3,-1,-3,5,3,6,7], k 3输出[3,3,5,5,6,7]约束1 ≤ k ≤ nums.length ≤ 10⁵进阶思路这题不能只用双指针——需要 O(1) 时间知道窗口最大值。用单调双端队列Monotonic Deque队首始终保持当前窗口最大值。fromcollectionsimportdequedefmaxSlidingWindow(nums:list[int],k:int)-list[int]:dqdeque()# 存下标保证对应值递减result[]fori,numinenumerate(nums):# 移除超出窗口左边界的下标ifdqanddq[0]i-k:dq.popleft()# 保持队列单调递减新元素比队尾大队尾就出队whiledqandnums[dq[-1]]num:dq.pop()dq.append(i)# 窗口形成后开始记录结果ifik-1:result.append(nums[dq[0]])returnresultpublicint[]maxSlidingWindow(int[]nums,intk){DequeIntegerdqnewArrayDeque();intnnums.length;int[]resnewint[n-k1];for(inti0;in;i){if(!dq.isEmpty()dq.peekFirst()i-k)dq.pollFirst();while(!dq.isEmpty()nums[dq.peekLast()]nums[i])dq.pollLast();dq.offerLast(i);if(ik-1)res[i-k1]nums[dq.peekFirst()];}returnres;}时间复杂度 O(n)每个元素入队出队各一次。这是滑动窗口 单调队列的经典组合面试高频。️ 真实产品场景场景 1Twitter/NETFLIX Trending Topics固定窗口需求给定过去 1 小时的所有 hashtag 序列找出任意 10 分钟窗口内出现次数最多的 hashtag。滑动窗口思路维护一个固定 10 分钟的时间窗口用 HashMap 计数每个 hashtag 的频率。窗口滑动时移除窗口左边过期的 hashtag添加右边新进来的。O(n) 时间就能找到最佳 10 分钟窗口。deffind_peak_window(hashtags:list[tuple[int,str]],window_ms:int): hashtags: [(timestamp_ms, tag), ...] 返回窗口内出现频率最高的 tag 和对应频率 fromcollectionsimportCounter counterCounter()left0best_tag,best_countNone,0forright,(ts,tag)inenumerate(hashtags):counter[tag]1# 滑动踢出窗口外的旧数据whilehashtags[right][0]-hashtags[left][0]window_ms:old_taghashtags[left][1]counter[old_tag]-1ifcounter[old_tag]0:delcounter[old_tag]left1# 当前最佳most_commoncounter.most_common(1)[0]ifmost_common[1]best_count:best_tag,best_countmost_commonreturnbest_tag,best_count场景 2广告频控可变窗口需求用户在最近 N 秒内最多看到 K 次广告。给定广告展示时间戳序列判断每个新广告是否允许展示。fromcollectionsimportdequeclassAdFrequencyController:def__init__(self,max_ads:int,window_seconds:int):self.max_adsmax_ads self.window_secondswindow_seconds self.timestampsdeque()defcan_show(self,current_time:float)-bool:# 清理过期时间戳whileself.timestampsandcurrent_time-self.timestamps[0]self.window_seconds:self.timestamps.popleft()iflen(self.timestamps)self.max_ads:self.timestamps.append(current_time)returnTruereturnFalse这个实现中 dequeue 就是滑动窗口的容器——右进左出O(1) 判断频控。⚡ 面试考点考察维度评分标准加分项问题识别能说出这题用滑动窗口 vs 前缀和的区别主动分析数组中是否有负数模板熟练度3 分钟内写出可变窗口模板边界处理无 bugleft 越界、空数组复杂度分析能解释为什么 left 走 n 步但总复杂度仍是 O(n)用均摊分析证明 left 最多走 n 步变体能力能处理固定窗口和可变窗口的切换能进阶到单调队列Hard常见踩坑忘记在while收缩循环里检查left right窗口状态用dict时忘记del为 0 的 key导致len()不准固定窗口场景忘了前 k-1 步不判断 同类题推荐题目难度一句话思路Permutation in String (LeetCode 567)Medium固定窗口 频率计数匹配Fruit Into Baskets (LeetCode 904)Medium可变窗口最多两种水果 窗口内最多两种字符Max Consecutive Ones III (LeetCode 1004)Medium可变窗口允许翻转 k 个 0 → 窗口内 0 的个数 ≤ k来源说明✅ 已验证LeetCode 官方题解 多轮 AI 验证 参考资料《算法导论》第 4 章分治策略中最大子数组问题与滑动窗口的对比 本文属于「算法体系课」第 2 课滑动窗口模式 发布信息主标题刷了 200 题才发现滑动窗口的 O(n) 不是运气是两条指针各走一遍备选标题面试官问我滑动窗口为什么是 O(n)我用两个指针解释明白了别再暴力枚举子数组了——滑动窗口的 O(n) 解法一次讲透从 Netflix 热榜到广告频控滑动窗口到底有多能打摘要滑动窗口模式深度拆解不是简单的 O(n²) 替代品而是一套处理连续性子问题的完整思维框架。含通用代码模板、3 道经典题Easy→Hard、2 个真实产品落地场景。算法体系课第 2 课。
刷了 200 题才发现：滑动窗口的 O(n) 不是运气，是两条指针各走一遍
发布时间：2026/6/20 21:31:00
一句话理解滑动窗口 两个指针圈出一段合法区间。右指针只管往前跑左指针在后面追——像截视频时拖那个选区框你只关心框里的东西。 本文产出滑动窗口模式的通用代码模板可直接复制3 道由浅入深的经典面试题 完整解题思路2 个真实产品场景Netflix trending topics / 广告投放频控面试官视角的评分要点❓ 这个模式解决什么问题一句话定义给定一个序列数组/字符串找一个满足某种约束条件的连续子序列时用滑动窗口在 O(n) 时间内解决。核心洞见暴力法把每个子数组从头算一遍O(n²)。但如果你只盯着当前窗口每次滑动时只做增量更新——加一个、减一个——那就降到 O(n) 了。不适用的情况别看到子数组就无脑套滑动窗口。下面这三种情况套了反而更麻烦❌ 不适合原因该用什么要求子序列但不要求连续窗口要求连续性动态规划 / 双指针数组中有负数固定目标和的场景右移不一定增大窗口和前缀和 HashMap需要精确匹配某个最小值/最大值的子数组数约束不满足向右扩张时单调前缀和 计数简单口诀有负数别用滑动窗口求目标和除非是变体非连续子序列别用滑动窗口。 模式识别什么样的题用滑动窗口特征说明示例题要求连续子数组/子串题目明确说连续或subarray最长无重复子串存在单调性右边界扩张后不满足条件时只能收缩左边界和 ≥ target 的最短子数组需要最优值min/max 某个窗口属性滑动窗口最大值窗口状态可增量更新加一个元素、删一个元素时O(1) 更新状态字符频率计数固定窗口 vs 可变窗口固定窗口窗口大小 k 是给定的 → for 循环套一个 if 条件 可变窗口窗口大小不固定 → while 循环收缩左边界判断方法看题目是否给了固定窗口大小 k。给了 → 固定窗口模板没给 → 可变窗口模板。 代码模板模板 A固定窗口deffixed_sliding_window(arr,k): 固定大小窗口模板 适用场景窗口大小 k 已知求窗口内某属性的最大/最小值 window_sum0best0forrightinrange(len(arr)):# 1. 扩张加入右边新元素window_sumarr[right]# 2. 判断窗口是否形成前 k-1 次循环先积累不判断ifrightk-1:continue# 3. 窗口形成更新答案bestmax(best,window_sum)# 4. 收缩移除左边过期元素准备下一次滑动leftright-k1window_sum-arr[left]returnbest模板 B可变窗口defvariable_sliding_window(s): 可变大小窗口模板 适用场景寻找满足某条件的最短/最长子串 fromcollectionsimportCounter windowCounter()# 或 set / dict取决于需要什么状态left0best0forrightinrange(len(s)):# 1. 扩张加入右边新元素window[s[right]]1# 2. 收缩当条件不满足时持续移动左边界直到恢复合法whilenotis_valid(window):# 条件因题而异window[s[left]]-1ifwindow[s[left]]0:delwindow[s[left]]left1# 3. 此时窗口内状态合法更新答案bestmax(best,right-left1)returnbest记忆口诀“右边进左边出合法时才记录”// Java 版 可变窗口模板publicintvariableWindow(Strings){MapCharacter,IntegerwindownewHashMap();intleft0,best0;for(intright0;rights.length();right){// 扩张charcs.charAt(right);window.merge(c,1,Integer::sum);// 收缩while(!isValid(window)){chards.charAt(left);window.merge(d,-1,Integer::sum);if(window.get(d)0)window.remove(d);left;}// 合法状态更新答案bestMath.max(best,right-left1);}returnbest;}️ 核心原理滑动窗口的本质增量更新 双指针协调是否右指针 right不断扩张窗口状态变化O(1) 增量更新窗口合法?更新最优解左指针 left 追赶恢复合法性right 继续前进为什么暴力法是 O(n²) 而不是 O(n)暴力法的问题在于每次窗口变化都重新计算状态滑动窗口 O(n)暴力法 O(n²)滑动窗口 O(n)暴力法 O(n²)枚举所有子数组 (i,j)指针协调各走 O(n)i0, j0..n-1 遍历 O(n)i1, j1..n-1 遍历 O(n-1)...共 O(n²) 次right 从 0 走到 n-1n 步left 从 0 最多走到 n-1n 步总计 2n O(n)关键差异暴力法每次重新计算滑动窗口复用上一次的结果只做增量修改。 三题进阶第 1 题MediumLongest Substring Without Repeating Characters原题给定字符串 s找出不含重复字符的最长子串的长度。项目内容输入s “abcabcbb”输出3“abc” 或 “bca” 或 “cab”约束0 ≤ s.length ≤ 5×10⁴字符集为 ASCII解题思路维护一个set记录当前窗口内的字符right扩张如果新字符已在 set 中说明出现重复left追赶从 set 中移除字符直到重复字符被踢出每次窗口合法时更新最长长度deflengthOfLongestSubstring(s:str)-int:seenset()left0best0forright,chinenumerate(s):whilechinseen:# 出现重复收缩seen.remove(s[left])left1seen.add(ch)# 加入新字符bestmax(best,right-left1)returnbestpublicintlengthOfLongestSubstring(Strings){SetCharacterseennewHashSet();intleft0,best0;for(intright0;rights.length();right){charcs.charAt(right);while(seen.contains(c)){seen.remove(s.charAt(left));left;}seen.add(c);bestMath.max(best,right-left1);}returnbest;}时间复杂度 O(n)空间 O(min(n, 字符集大小))。第 2 题MediumMinimum Size Subarray Sum原题给定正整数数组 nums 和目标值 target找出和 ≥ target 的最短连续子数组长度。项目内容输入target 7, nums [2,3,1,2,4,3]输出2子数组 [4,3] 的和 7约束1 ≤ target ≤ 10⁹1 ≤ nums.length ≤ 10⁵为什么可以用滑动窗口数组元素全是正整数 → 窗口扩张时和一定增大收缩时和一定减小。单调性成立。defminSubArrayLen(target:int,nums:list[int])-int:left0window_sum0bestfloat(inf)forrightinrange(len(nums)):window_sumnums[right]# 扩张whilewindow_sumtarget:# 满足条件尝试收缩bestmin(best,right-left1)window_sum-nums[left]left1returnbestifbest!float(inf)else0陷阱提示如果 nums 中有负数如 [-1, 2, 3]不能直接用滑动窗口——扩张不一定增加和收缩不一定减少和。此时要用前缀和。第 3 题HardSliding Window Maximum原题给定数组 nums 和窗口大小 k返回每个窗口中最大值的数组。项目内容输入nums [1,3,-1,-3,5,3,6,7], k 3输出[3,3,5,5,6,7]约束1 ≤ k ≤ nums.length ≤ 10⁵进阶思路这题不能只用双指针——需要 O(1) 时间知道窗口最大值。用单调双端队列Monotonic Deque队首始终保持当前窗口最大值。fromcollectionsimportdequedefmaxSlidingWindow(nums:list[int],k:int)-list[int]:dqdeque()# 存下标保证对应值递减result[]fori,numinenumerate(nums):# 移除超出窗口左边界的下标ifdqanddq[0]i-k:dq.popleft()# 保持队列单调递减新元素比队尾大队尾就出队whiledqandnums[dq[-1]]num:dq.pop()dq.append(i)# 窗口形成后开始记录结果ifik-1:result.append(nums[dq[0]])returnresultpublicint[]maxSlidingWindow(int[]nums,intk){DequeIntegerdqnewArrayDeque();intnnums.length;int[]resnewint[n-k1];for(inti0;in;i){if(!dq.isEmpty()dq.peekFirst()i-k)dq.pollFirst();while(!dq.isEmpty()nums[dq.peekLast()]nums[i])dq.pollLast();dq.offerLast(i);if(ik-1)res[i-k1]nums[dq.peekFirst()];}returnres;}时间复杂度 O(n)每个元素入队出队各一次。这是滑动窗口 单调队列的经典组合面试高频。️ 真实产品场景场景 1Twitter/NETFLIX Trending Topics固定窗口需求给定过去 1 小时的所有 hashtag 序列找出任意 10 分钟窗口内出现次数最多的 hashtag。滑动窗口思路维护一个固定 10 分钟的时间窗口用 HashMap 计数每个 hashtag 的频率。窗口滑动时移除窗口左边过期的 hashtag添加右边新进来的。O(n) 时间就能找到最佳 10 分钟窗口。deffind_peak_window(hashtags:list[tuple[int,str]],window_ms:int): hashtags: [(timestamp_ms, tag), ...] 返回窗口内出现频率最高的 tag 和对应频率 fromcollectionsimportCounter counterCounter()left0best_tag,best_countNone,0forright,(ts,tag)inenumerate(hashtags):counter[tag]1# 滑动踢出窗口外的旧数据whilehashtags[right][0]-hashtags[left][0]window_ms:old_taghashtags[left][1]counter[old_tag]-1ifcounter[old_tag]0:delcounter[old_tag]left1# 当前最佳most_commoncounter.most_common(1)[0]ifmost_common[1]best_count:best_tag,best_countmost_commonreturnbest_tag,best_count场景 2广告频控可变窗口需求用户在最近 N 秒内最多看到 K 次广告。给定广告展示时间戳序列判断每个新广告是否允许展示。fromcollectionsimportdequeclassAdFrequencyController:def__init__(self,max_ads:int,window_seconds:int):self.max_adsmax_ads self.window_secondswindow_seconds self.timestampsdeque()defcan_show(self,current_time:float)-bool:# 清理过期时间戳whileself.timestampsandcurrent_time-self.timestamps[0]self.window_seconds:self.timestamps.popleft()iflen(self.timestamps)self.max_ads:self.timestamps.append(current_time)returnTruereturnFalse这个实现中 dequeue 就是滑动窗口的容器——右进左出O(1) 判断频控。⚡ 面试考点考察维度评分标准加分项问题识别能说出这题用滑动窗口 vs 前缀和的区别主动分析数组中是否有负数模板熟练度3 分钟内写出可变窗口模板边界处理无 bugleft 越界、空数组复杂度分析能解释为什么 left 走 n 步但总复杂度仍是 O(n)用均摊分析证明 left 最多走 n 步变体能力能处理固定窗口和可变窗口的切换能进阶到单调队列Hard常见踩坑忘记在while收缩循环里检查left right窗口状态用dict时忘记del为 0 的 key导致len()不准固定窗口场景忘了前 k-1 步不判断 同类题推荐题目难度一句话思路Permutation in String (LeetCode 567)Medium固定窗口 频率计数匹配Fruit Into Baskets (LeetCode 904)Medium可变窗口最多两种水果 窗口内最多两种字符Max Consecutive Ones III (LeetCode 1004)Medium可变窗口允许翻转 k 个 0 → 窗口内 0 的个数 ≤ k来源说明✅ 已验证LeetCode 官方题解 多轮 AI 验证 参考资料《算法导论》第 4 章分治策略中最大子数组问题与滑动窗口的对比 本文属于「算法体系课」第 2 课滑动窗口模式 发布信息主标题刷了 200 题才发现滑动窗口的 O(n) 不是运气是两条指针各走一遍备选标题面试官问我滑动窗口为什么是 O(n)我用两个指针解释明白了别再暴力枚举子数组了——滑动窗口的 O(n) 解法一次讲透从 Netflix 热榜到广告频控滑动窗口到底有多能打摘要滑动窗口模式深度拆解不是简单的 O(n²) 替代品而是一套处理连续性子问题的完整思维框架。含通用代码模板、3 道经典题Easy→Hard、2 个真实产品落地场景。算法体系课第 2 课。
