Sliding Window（滑动窗口）

Sliding Window（滑动窗口）

滑动窗口主要用于处理连续子数组或子字符串的问题，核心是在线性时间内通过两个指针维护一个“窗口”，当窗口不满足条件时移动左指针（收缩），当窗口需要扩展时移动右指针（扩展）。

什么时候用滑动窗口？

• 输入是数组或字符串
• 要求寻找满足某种条件的连续子序列（子数组、子串）
  常见条件：和 ≥ target，包含至多 K 个不同字符，无重复字符，等等
• 数据本身不一定有序，但窗口的左右边界移动有单调性

滑动窗口分类

1. 变长窗口：不限制窗口大小，根据条件动态调整（最常见，如第3题、第340题）
2. 定长窗口：窗口大小固定为 K，只需滑动一次（如第239题，但我们用单调队列做，后面会讲）

本专题两题都是变长窗口。

1. 核心模板（变长滑动窗口）

intleft=0,res=0;for(intright=0;right<arr.length;right++){// 1. 将 right 元素加入窗口，更新窗口状态...// 2. 当窗口不满足条件时，收缩 leftwhile(窗口不满足条件){// 移除 left 元素，更新窗口状态left++;}// 3. 此时窗口满足条件，更新答案res=max/min(res,right-left+1);}returnres;

其中“窗口状态”常由HashMap或计数数组维护，用于跟踪字符频率或元素和等。

2. 例题一：无重复字符的最长子串（3. Longest Substring Without Repeating Characters, Medium）

题目：给定一个字符串s，找出其中不含有重复字符的最长子串的长度。

示例：
输入:"abcabcbb"→ 输出:3（"abc"）
输入:"bbbbb"→ 输出:1（"b"）

思路

维护一个窗口[left, right]，里面没有重复字符。用HashSet或HashMap记录窗口内字符。
当右指针遇到重复字符时，说明窗口不满足条件，此时必须将左指针右移，并移除对应字符，直到窗口内不再有重复。
每次窗口内无重复时，记录当前窗口长度。

代码（HashSet 版）

publicintlengthOfLongestSubstring(Strings){Set<Character>set=newHashSet<>();intleft=0,maxLen=0;for(intright=0;right<s.length();right++){charc=s.charAt(right);// 如果加入后出现重复，就收缩左边界直到不重复while(set.contains(c)){set.remove(s.charAt(left));left++;}set.add(c);maxLen=Math.max(maxLen,right-left+1);}returnmaxLen;}

优化：可以用HashMap记录每个字符上次出现的位置，直接让left跳到上次位置+1，避免一个个移动，但思想一样，仍然是滑动窗口。

3. 例题二：长度最小的子数组（209. Minimum Size Subarray Sum, Medium）

题目：给定一个含有正整数的数组nums和一个正整数target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在，返回 0。

示例：
target = 7, nums = [2,3,1,2,4,3]→ 输出2（子数组[4,3]）

思路

同样使用变长窗口。维护窗口内元素之和sum。
当sum >= target时，尝试收缩左边界，因为要找最小长度；收缩过程中一直更新最小长度。
当sum < target时，扩展右边界。

代码

publicintminSubArrayLen(inttarget,int[]nums){intleft=0,sum=0,minLen=Integer.MAX_VALUE;for(intright=0;right<nums.length;right++){sum+=nums[right];while(sum>=target){// 满足条件，尝试缩小窗口minLen=Math.min(minLen,right-left+1);sum-=nums[left];left++;}}returnminLen==Integer.MAX_VALUE?0:minLen;}

复杂度：每个元素最多被加入一次和移出一次，O(n)时间，O(1)额外空间。

4. 延伸：至多 K 个不同字符的最长子串（340. Longest Substring with At Most K Distinct Characters, Medium）

这道题在 PDF 第 12 页作为滑动窗口的经典例子，可以加深对模板的理解。

题目：给定字符串s和整数k，返回包含至多k种不同字符的最长子串的长度。

思路：用HashMap记录窗口内每个字符的出现次数。当map.size() > k时收缩左边界，并更新计数，直到不同字符数 ≤ k。

代码：

publicintlengthOfLongestSubstringKDistinct(Strings,intk){Map<Character,Integer>map=newHashMap<>();intleft=0,maxLen=0;for(intright=0;right<s.length();right++){charcur=s.charAt(right);map.put(cur,map.getOrDefault(cur,0)+1);while(map.size()>k){charleftChar=s.charAt(left);map.put(leftChar,map.get(leftChar)-1);if(map.get(leftChar)==0)map.remove(leftChar);left++;}maxLen=Math.max(maxLen,right-left+1);}returnmaxLen;}

这个模板和前面的完全一致，只是“窗口不满足条件”的判断变成了map.size() > k。

总结：滑动窗口模板化

核心三步：

1. 扩展右边界，更新窗口状态
2. 当窗口不满足条件时，收缩左边界
3. 窗口满足条件后，更新答案（最大值通常收缩后更新，最小值在收缩过程中更新）