Sliding Window（滑动窗口）

Sliding Window滑动窗口滑动窗口主要用于处理连续子数组或子字符串的问题核心是在线性时间内通过两个指针维护一个“窗口”当窗口不满足条件时移动左指针收缩当窗口需要扩展时移动右指针扩展。什么时候用滑动窗口输入是数组或字符串要求寻找满足某种条件的连续子序列子数组、子串常见条件和 ≥ target包含至多 K 个不同字符无重复字符等等数据本身不一定有序但窗口的左右边界移动有单调性滑动窗口分类变长窗口不限制窗口大小根据条件动态调整最常见如第3题、第340题定长窗口窗口大小固定为 K只需滑动一次如第239题但我们用单调队列做后面会讲本专题两题都是变长窗口。1. 核心模板变长滑动窗口intleft0,res0;for(intright0;rightarr.length;right){// 1. 将 right 元素加入窗口更新窗口状态...// 2. 当窗口不满足条件时收缩 leftwhile(窗口不满足条件){// 移除 left 元素更新窗口状态left;}// 3. 此时窗口满足条件更新答案resmax/min(res,right-left1);}returnres;其中“窗口状态”常由HashMap或计数数组维护用于跟踪字符频率或元素和等。2. 例题一无重复字符的最长子串3. Longest Substring Without Repeating Characters, Medium题目给定一个字符串s找出其中不含有重复字符的最长子串的长度。示例输入:abcabcbb→ 输出:3abc输入:bbbbb→ 输出:1b思路维护一个窗口[left, right]里面没有重复字符。用HashSet或HashMap记录窗口内字符。当右指针遇到重复字符时说明窗口不满足条件此时必须将左指针右移并移除对应字符直到窗口内不再有重复。每次窗口内无重复时记录当前窗口长度。代码HashSet 版publicintlengthOfLongestSubstring(Strings){SetCharactersetnewHashSet();intleft0,maxLen0;for(intright0;rights.length();right){charcs.charAt(right);// 如果加入后出现重复就收缩左边界直到不重复while(set.contains(c)){set.remove(s.charAt(left));left;}set.add(c);maxLenMath.max(maxLen,right-left1);}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){intleft0,sum0,minLenInteger.MAX_VALUE;for(intright0;rightnums.length;right){sumnums[right];while(sumtarget){// 满足条件尝试缩小窗口minLenMath.min(minLen,right-left1);sum-nums[left];left;}}returnminLenInteger.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){MapCharacter,IntegermapnewHashMap();intleft0,maxLen0;for(intright0;rights.length();right){charcurs.charAt(right);map.put(cur,map.getOrDefault(cur,0)1);while(map.size()k){charleftChars.charAt(left);map.put(leftChar,map.get(leftChar)-1);if(map.get(leftChar)0)map.remove(leftChar);left;}maxLenMath.max(maxLen,right-left1);}returnmaxLen;}这个模板和前面的完全一致只是“窗口不满足条件”的判断变成了map.size() k。总结滑动窗口模板化问题类型窗口维护的内容收缩条件更新答案时机无重复字符最长子串字符出现与否Set发现重复字符收缩后窗口内无重复和 ≥ target最短子数组元素之和sum ≥ target收缩过程中每次满足条件至多K个不同字符最长子串字符频率Map不同字符数 k收缩后满足条件核心三步扩展右边界更新窗口状态当窗口不满足条件时收缩左边界窗口满足条件后更新答案最大值通常收缩后更新最小值在收缩过程中更新