刷了 200 题才发现：滑动窗口的 O(n) 不是运气，是两条指针各走一遍

一句话理解：滑动窗口 = 两个指针圈出一段"合法区间"。右指针只管往前跑，左指针在后面追——像截视频时拖那个选区框，你只关心框里的东西。

🎯 本文产出

• 滑动窗口模式的通用代码模板（可直接复制）
• 3 道由浅入深的经典面试题 + 完整解题思路
• 2 个真实产品场景（Netflix trending topics / 广告投放频控）
• 面试官视角的评分要点

❓ 这个模式解决什么问题

一句话定义：给定一个序列（数组/字符串），找一个满足某种约束条件的连续子序列时，用滑动窗口在 O(n) 时间内解决。

核心洞见：暴力法把每个子数组从头算一遍，O(n²)。但如果你只盯着当前窗口，每次滑动时只做增量更新——加一个、减一个——那就降到 O(n) 了。

不适用的情况

别看到"子数组"就无脑套滑动窗口。下面这三种情况，套了反而更麻烦：

简单口诀：有负数别用滑动窗口求目标和（除非是变体），非连续子序列别用滑动窗口。

🧩 模式识别：什么样的题用滑动窗口

固定窗口 vs 可变窗口

固定窗口：窗口大小 k 是给定的 → for 循环套一个 if 条件 可变窗口：窗口大小不固定 → while 循环收缩左边界

判断方法：看题目是否给了固定窗口大小 k。给了 → 固定窗口模板；没给 → 可变窗口模板。

💻 代码模板

模板 A：固定窗口

deffixed_sliding_window(arr,k):""" 固定大小窗口模板 适用场景：窗口大小 k 已知，求窗口内某属性的最大/最小值 """window_sum=0best=0forrightinrange(len(arr)):# 1. 扩张：加入右边新元素window_sum+=arr[right]# 2. 判断窗口是否形成（前 k-1 次循环先积累，不判断）ifright<k-1:continue# 3. 窗口形成，更新答案best=max(best,window_sum)# 4. 收缩：移除左边过期元素（准备下一次滑动）left=right-k+1window_sum-=arr[left]returnbest

模板 B：可变窗口

defvariable_sliding_window(s):""" 可变大小窗口模板 适用场景：寻找满足某条件的最短/最长子串 """fromcollectionsimportCounter window=Counter()# 或 set / dict，取决于需要什么状态left=0best=0forrightinrange(len(s)):# 1. 扩张：加入右边新元素window[s[right]]+=1# 2. 收缩：当条件不满足时，持续移动左边界直到恢复合法whilenotis_valid(window):# 条件因题而异window[s[left]]-=1ifwindow[s[left]]==0:delwindow[s[left]]left+=1# 3. 此时窗口内状态合法，更新答案best=max(best,right-left+1)returnbest

记忆口诀：“右边进，左边出，合法时才记录”

// Java 版 可变窗口模板publicintvariableWindow(Strings){Map<Character,Integer>window=newHashMap<>();intleft=0,best=0;for(intright=0;right<s.length();right++){// 扩张charc=s.charAt(right);window.merge(c,1,Integer::sum);// 收缩while(!isValid(window)){chard=s.charAt(left);window.merge(d,-1,Integer::sum);if(window.get(d)==0)window.remove(d);left++;}// 合法状态，更新答案best=Math.max(best,right-left+1);}returnbest;}

🏗️ 核心原理

滑动窗口的本质：增量更新 + 双指针协调

为什么暴力法是 O(n²) 而不是 O(n)

暴力法的问题在于每次窗口变化都重新计算状态：

关键差异：暴力法每次重新计算，滑动窗口复用上一次的结果，只做增量修改。

🎯 三题进阶

第 1 题（Medium）：Longest Substring Without Repeating Characters

原题：给定字符串 s，找出不含重复字符的最长子串的长度。

解题思路：

1. 维护一个set记录当前窗口内的字符
2. right扩张，如果新字符已在 set 中，说明出现重复
3. left追赶，从 set 中移除字符，直到重复字符被踢出
4. 每次窗口合法时，更新最长长度

deflengthOfLongestSubstring(s:str)->int:seen=set()left=0best=0forright,chinenumerate(s):whilechinseen:# 出现重复，收缩seen.remove(s[left])left+=1seen.add(ch)# 加入新字符best=max(best,right-left+1)returnbest

publicintlengthOfLongestSubstring(Strings){Set<Character>seen=newHashSet<>();intleft=0,best=0;for(intright=0;right<s.length();right++){charc=s.charAt(right);while(seen.contains(c)){seen.remove(s.charAt(left));left++;}seen.add(c);best=Math.max(best,right-left+1);}returnbest;}

时间复杂度 O(n)，空间 O(min(n, 字符集大小))。

第 2 题（Medium）：Minimum Size Subarray Sum

原题：给定正整数数组 nums 和目标值 target，找出和 ≥ target 的最短连续子数组长度。

为什么可以用滑动窗口：数组元素全是正整数 → 窗口扩张时和一定增大，收缩时和一定减小。单调性成立。

defminSubArrayLen(target:int,nums:list[int])->int:left=0window_sum=0best=float('inf')forrightinrange(len(nums)):window_sum+=nums[right]# 扩张whilewindow_sum>=target:# 满足条件，尝试收缩best=min(best,right-left+1)window_sum-=nums[left]left+=1returnbestifbest!=float('inf')else0

陷阱提示：如果 nums 中有负数（如 [-1, 2, 3]），不能直接用滑动窗口——扩张不一定增加和，收缩不一定减少和。此时要用前缀和。

第 3 题（Hard）：Sliding Window Maximum

原题：给定数组 nums 和窗口大小 k，返回每个窗口中最大值的数组。

进阶思路：这题不能只用双指针——需要 O(1) 时间知道窗口最大值。用单调双端队列（Monotonic Deque），队首始终保持当前窗口最大值。

fromcollectionsimportdequedefmaxSlidingWindow(nums:list[int],k:int)->list[int]:dq=deque()# 存下标，保证对应值递减result=[]fori,numinenumerate(nums):# 移除超出窗口左边界的下标ifdqanddq[0]<=i-k:dq.popleft()# 保持队列单调递减：新元素比队尾大，队尾就出队whiledqandnums[dq[-1]]<=num:dq.pop()dq.append(i)# 窗口形成后开始记录结果ifi>=k-1:result.append(nums[dq[0]])returnresult

publicint[]maxSlidingWindow(int[]nums,intk){Deque<Integer>dq=newArrayDeque<>();intn=nums.length;int[]res=newint[n-k+1];for(inti=0;i<n;i++){if(!dq.isEmpty()&&dq.peekFirst()<=i-k)dq.pollFirst();while(!dq.isEmpty()&&nums[dq.peekLast()]<=nums[i])dq.pollLast();dq.offerLast(i);if(i>=k-1)res[i-k+1]=nums[dq.peekFirst()];}returnres;}

时间复杂度 O(n)，每个元素入队出队各一次。这是滑动窗口 + 单调队列的经典组合，面试高频。

🏗️ 真实产品场景

场景 1：Twitter/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 counter=Counter()left=0best_tag,best_count=None,0forright,(ts,tag)inenumerate(hashtags):counter[tag]+=1# 滑动：踢出窗口外的旧数据whilehashtags[right][0]-hashtags[left][0]>window_ms:old_tag=hashtags[left][1]counter[old_tag]-=1ifcounter[old_tag]==0:delcounter[old_tag]left+=1# 当前最佳most_common=counter.most_common(1)[0]ifmost_common[1]>best_count:best_tag,best_count=most_commonreturnbest_tag,best_count

场景 2：广告频控（可变窗口）

需求：用户在最近 N 秒内最多看到 K 次广告。给定广告展示时间戳序列，判断每个新广告是否允许展示。

fromcollectionsimportdequeclassAdFrequencyController:def__init__(self,max_ads:int,window_seconds:int):self.max_ads=max_ads self.window_seconds=window_seconds self.timestamps=deque()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) 判断频控。

⚡ 面试考点

常见踩坑：

• 忘记在while收缩循环里检查left <= right
• 窗口状态用dict时忘记del为 0 的 key（导致len()不准）
• 固定窗口场景忘了前 k-1 步不判断

📝 同类题推荐

来源说明：

• ✅ 已验证：LeetCode 官方题解 + 多轮 AI 验证
• 📄 参考资料：《算法导论》第 4 章分治策略中"最大子数组问题"与滑动窗口的对比
• 🎓 本文属于「算法体系课」第 2 课：滑动窗口模式

📋 发布信息

• 主标题：刷了 200 题才发现：滑动窗口的 O(n) 不是运气，是两条指针各走一遍
• 备选标题：
  1. 面试官问我滑动窗口为什么是 O(n)，我用两个指针解释明白了
  2. 别再暴力枚举子数组了——滑动窗口的 O(n) 解法一次讲透
  3. 从 Netflix 热榜到广告频控，滑动窗口到底有多能打
• 摘要：滑动窗口模式深度拆解：不是简单的 O(n²) 替代品，而是一套处理连续性子问题的完整思维框架。含通用代码模板、3 道经典题（Easy→Hard）、2 个真实产品落地场景。算法体系课第 2 课。