1 .滑动窗口算法探究1.1“图”滑动窗口算法[a、b、c、d、e、f、g、 ] lr [初始化窗口，r ] l r [维护窗口数据信息，窗口窗口数据满足某个条件，r]LR窗口数据不满足某个条件，维持窗口数据信息。 l (小循环直到窗口数据满足某个条件)，更新结果。 r ) . 1.2滑动窗口算法模板代码public int [ ] slidewindowtemplate (intnums ) intL=0，r=0； //[初始化窗口] //codes. [其他初始化信息]while(rnums.length )] //codes. [维护窗口中的数据]while(lrcheck(XXX )=//[增大窗口] }} 1.3模板leetcode [3]最长不重复子串【中等】【主题】:给定某个字符串查找最长不重复子串【问题解决】:首先维护滑动窗口当前很明显，要确定是否出现了某个东西，哈希表是一种理想的方法。 因此，我们要设置模板。 publicintlengthoflongestsubstring (字符串) { int l=-1，r=0； //初始化窗口int res=0； //初始化结果信息MapCharacter，Integer map=new HashMap (； ///这里初始化散列表，存储各个字符的最后的出现位置while(rs.length ) (charc=map.get ) r )。 //现在检查一下窗口中字符的唯一性。 如果不唯一，则必须缩小窗口，如上面的check () while ) map.containskey ) l=map.get(c ) c ) ) l。 }map.put(s.Charat(r )，r )； //散列表RES=math.max(RES，r - l )维护； //更新结果r； //打开窗口}返回RES； }可视化
[a b c a b c b b] lr [init，{a:0}，res=0，res=1，r ] l r [check fail，{a:0，b:1}，res=2，r ] lr [ checheck r]Lr[cheeck] c:2}，res=3，r ] l r [check succ，l，{a:3，b:1，c:2}，res=3，r ] . 然后，这里散列表不是窗口内的信息，而是全局信息，但是基本还是成功的，基础结构一致，需要维护什么信息需要根据题目条件来设定
2 .滑动窗口例题2.1例题一leetcode[424]替换后的最长重复字符【题目】中给出只由大写字母组成的字符串。 任何位置的字符都可以替换为另一个字符，最多可以替换k次。 执行上述操作后，找到包含重复字符的最长子列的长度。 本问题直接应用模板，通过检查窗口中的字符是否可以更改k个，得到连续的重复字符串publicintyhdGB(strings，int k ) ) intL=0，r=0，RES int maxCount=0； HashMapCharacter，Integer map=new HashMap (； while(rs.Length ) (charc=s.charat ) )； map.put(c，map.getOrDe
fault(c,0) + 1); maxCount = Math.max(maxCount,map.get(c)); //维护窗口信息 while(r - l + 1 > maxCount + k){ //check 检查窗口中数据性质 char l = s.charAt(l); map.put(l,map.get(l) - 1); l++; //收缩 } res = Math.max(res, r - l + 1); //更新结果 r++; //扩张 } return res;}可视化
[fzdxb] , k = 1 lr [{A:1}, maxCount = 1, res = 1, r++] l r [{A:2}, maxCount = 2, res = 2, r++] l r [{A:2,B:1}, maxCount = 2, res = 3, r++] l r [{A:3,B:1}, maxCount = 3, {A:2,B:1}, l++, res = 3, r++] l r [{A:2,B:2}, maxCount = 2, {A:1,B:2}, l++, res = 3, r++] ...... 2.2 例题2 leetcode [395] 带有至少K个重复字符的最长子字符串【题目】：找到给定字符串（由小写字符组成）中的最长子串T， 要求T中的每一字符出现次数都不少于k。输出T的长度。【题解】：这里可以维护一个滑动窗口来记录子串，判断子串中字符的重复次数。但还需要注意一点，通过分类，可以减少窗口中需要维护的信息量。这里先统计原始字符串中字符的种类，然后根据子串中的字符种类个数分类，例如子串中只有1种字符，只有2种字符，有3种字符等。 public int longestSubstring(String s, int k) { int res = 0; int maxUnique = getMaxUinqueCount(s); int[] countMap = new int[26]; //初始化map维护窗口字符统计信息 for(int curUnique = 1; curUnique <= maxUnique; curUnique++){ //根据子串中字符种类个数分别考虑 Arrays.fill(countMap, 0); int l = 0, r = 0, unique = 0, idx = 0, countAtLeastK = 0; //初始化窗口信息 while(r < s.length()){ //此处开始滑动窗口大循环 if(unique <= curUnique){ //窗口满足性质：字符种类数量不超过本轮设定值 idx = s.charAt(r) - 'a'; if(countMap[idx] == 0) unique++; //更新信息 countMap[idx]++; //更新信息 if(countMap[idx] == k) countAtLeastK++; //更新信息 r++; //窗口扩张 } else{ //窗口不满足性质：字符种类数量超过本轮设定值 idx = s.charAt(l) - 'a'; if(countMap[idx] == k) countAtLeastK--; countMap[idx]--; if(countMap[idx] == 0) unique--; l++; //窗口收缩 } if(unique == curUnique && unique == countAtLeastK) //窗口数据信息满足题目条件，更新结果 res = Math.max(r - l, res); } } return res;}public static int getMaxUinqueCount(String s){ //统计字符数量 Set<Character> set = new HashSet<>(); for(int i = 0; i < s.length(); i++){ set.add(s.charAt(i)); } return set.size();}可视化
[a b a b b c] unique = 1,2,3 以字符种类数为2为例，解析滑动窗口运行情况 lr [curUnique = 1 <= 2, {a:1}, r++, atLeastK = 0,] l r [curUnique = 2 <= 2, {a:1,b=1}, r++, atLeastK = 0, r++] l r [curUnique = 2 <= 2, {a:2,b=1}, r++, atLeastK = 1] l r [curUnique = 2 <= 2, {a:2,b=2}, r++, atLeastK = 2, res = max(res, r - l)] l r [curUnique = 2 <= 2, {a:2,b=3}, r++, atLeastK = 2, res = max(res, r - l)] l r [curUnique = 3 > 2, {a:2,b=3}, so atLeastK - 1 = 1, {a:1,b=3}, l++] l r end 2.3 例题3 leetcode [567] 字符串的排列【题目】：定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。【题解】：这里可以维护一个滑动窗口来记录s2子串，判断子串是否完全匹配s1,完全匹配指的是字符串中的所有字符的数量都相等。因此使用一个哈希表（这里用数组模拟）来记录s1的所有字符数量。 public boolean checkInclusion(String s1, String s2) { int l = 0, r = 0; int[] map = new int[26]; for(int i = 0; i < s1.length(); i++){ map[s1.charAt(i) - 'a']++; } while(r < s2.length()){ char c = s2.charAt(r); map[c - 'a']--; //窗口变动，维护哈希表 while(map[c - 'a'] < 0){ //检查是否完全匹配 map[s2.charAt(l) - 'a']++; l++; //窗口收缩 } if(r - l + 1 == s1.length()) return true; r++; //窗口扩张 } return false;} 2.4 其他例题使用该模版，可以解决如下问题
1004. Max Consecutive Ones III
1052. Grumpy Bookstore Owner
1208. Get Equal Substrings Within Budget
1456. Maximum Number of Vowels in a Substring of Given Length
76. Minimum Window Substring
稍加改变，可以解决如下问题
1498. Number of Subsequences That Satisfy the Given Sum Condition
1423. Maximum Points You Can Obtain from Cards
992. Subarrays with K Different Integers
3. 小结 套模版即可解决80%的滑动窗口题，剩余20%可能需要改变模型或进行时间优化滑动窗口算法关键在于收缩时需要持续收缩使得窗口数据某个需要保持的性质发生改变滑动窗口算法框架较为固定基本为 step 1: 初始化窗口端点lr、初始化其他需要维护的窗口信息或全局信息step 2: 进入大循环，直到窗口右端点到达末尾step 3: 大循环内，r所在位置进入窗口，维护窗口信息及全局信息step 4: 进入小循环，直到窗口中的数据部满足某个性质或条件step 5: 小循环内，维护窗口信息及全局信息，收缩窗口step 6: 小循环外，大循环内，更新结果，扩张窗口 滑动窗口特点是不回退、不回退、不回退由于其不回退的性质，时间复杂度通常为 O ( n ) O(n) O(n)