尧图网页设计 
1. 滑动窗口算法概述滑动窗口算法是一种高效的数组/字符串处理技巧它通过维护一个可变大小的窗口来遍历数据避免了暴力解法中不必要的重复计算。这种算法特别适合解决子数组/子字符串相关的问题比如寻找满足特定条件的最长子串、最短覆盖子串等。核心思想是使用两个指针通常称为左指针left和右指针right来定义窗口的边界。右指针负责扩展窗口左指针负责收缩窗口通过这种滑动的方式遍历整个数据集合。这种方法的优势在于它能够将时间复杂度从暴力解法的O(n²)降低到O(n)因为每个元素最多被访问两次。2. 滑动窗口的基本框架2.1 算法模板代码以下是滑动窗口算法的通用模板适用于大多数相关问题void slidingWindow(String s) { // 用于记录窗口内数据的哈希表 MapCharacter, Integer window new HashMap(); int left 0, right 0; // 初始化窗口边界 while (right s.length()) { // c是将移入窗口的字符 char c s.charAt(right); // 右移窗口 right; // 进行窗口内数据的一系列更新 // ... // 判断左侧窗口是否要收缩 while (window needs shrink) { // d是将移出窗口的字符 char d s.charAt(left); // 左移窗口 left; // 进行窗口内数据的一系列更新 // ... } } }2.2 关键问题解析使用滑动窗口算法时需要明确回答以下三个核心问题何时扩展窗口移动右指针通常是在当前窗口不满足条件时扩展窗口每次扩展后需要更新窗口内的数据统计何时收缩窗口移动左指针当窗口满足特定条件时开始收缩收缩是为了寻找更优解或满足新条件何时更新结果可能在扩展窗口时更新也可能在收缩窗口时更新取决于具体问题的要求3. 最小覆盖子串问题3.1 问题描述LeetCode第76题给定一个字符串S和一个字符串T在S中找到包含T所有字符的最短子串。示例 输入S ADOBECODEBANC, T ABC 输出BANC3.2 解题思路使用两个哈希表分别记录needT中字符的出现次数window当前窗口中包含T字符的出现次数使用valid变量统计窗口中满足need条件的字符数量滑动窗口过程扩展窗口直到包含T所有字符收缩窗口寻找更小的满足条件的子串记录最小子串的起始位置和长度3.3 完整实现代码public String minWindow(String s, String t) { MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); // 初始化need表 for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } int left 0, right 0; int valid 0; // 匹配的字符数 int start 0, len Integer.MAX_VALUE; // 结果记录 while (right s.length()) { char c s.charAt(right); right; // 更新窗口数据 if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } // 判断是否收缩窗口 while (valid need.size()) { // 更新最小子串 if (right - left len) { start left; len right - left; } char d s.charAt(left); left; // 更新窗口数据 if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return len Integer.MAX_VALUE ? : s.substring(start, start len); }4. 字符串排列问题4.1 问题描述LeetCode第567题给定两个字符串s1和s2判断s2是否包含s1的排列。示例 输入s1 ab, s2 eidbaooo 输出true 解释s2包含s1的排列ba4.2 解题思路这实际上是寻找一个固定长度s1长度的窗口窗口内的字符及其频率要与s1完全匹配使用与最小覆盖子串类似的滑动窗口方法当窗口大小等于s1长度时检查是否匹配4.3 完整实现代码public boolean checkInclusion(String s1, String s2) { MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); for (char c : s1.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } int left 0, right 0; int valid 0; while (right s2.length()) { char c s2.charAt(right); right; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } // 保持窗口大小等于s1长度 while (right - left s1.length()) { if (valid need.size()) { return true; } char d s2.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return false; }5. 找所有字母异位词5.1 问题描述LeetCode第438题给定一个字符串s和一个非空字符串p找到s中所有是p的字母异位词的子串返回这些子串的起始索引。示例 输入s cbaebabacd, p abc 输出[0,6] 解释 起始索引0的子串是cba 起始索引6的子串是bac5.2 解题思路这与字符串排列问题非常相似区别在于需要记录所有符合条件的子串起始位置窗口大小固定为p的长度使用列表收集所有满足条件的起始索引5.3 完整实现代码public ListInteger findAnagrams(String s, String p) { MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); ListInteger res new ArrayList(); for (char c : p.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } int left 0, right 0; int valid 0; while (right s.length()) { char c s.charAt(right); right; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } while (right - left p.length()) { if (valid need.size()) { res.add(left); } char d s.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return res; }6. 最长无重复字符子串6.1 问题描述LeetCode第3题给定一个字符串找出不含有重复字符的最长子串的长度。示例 输入abcabcbb 输出3 解释无重复字符的最长子串是abc6.2 解题思路使用滑动窗口维护当前无重复字符的子串当遇到重复字符时收缩窗口记录窗口的最大长度只需要一个哈希表记录字符最后出现的位置6.3 完整实现代码public int lengthOfLongestSubstring(String s) { MapCharacter, Integer window new HashMap(); int left 0, right 0; int res 0; while (right s.length()) { char c s.charAt(right); right; // 更新窗口数据 window.put(c, window.getOrDefault(c, 0) 1); // 当有重复字符时收缩窗口 while (window.get(c) 1) { char d s.charAt(left); left; window.put(d, window.get(d) - 1); } // 更新结果 res Math.max(res, right - left); } return res; }7. 滑动窗口算法优化技巧7.1 哈希表优化对于字符类问题可以使用固定大小的数组代替哈希表int[] need new int[128]; // ASCII码范围 for (char c : t.toCharArray()) { need[c]; }7.2 边界条件处理空字符串输入目标字符串比源字符串长目标字符串包含源字符串没有的字符7.3 复杂度分析时间复杂度O(n)每个元素最多被访问两次空间复杂度O(k)k是字符集大小8. 常见错误与调试技巧8.1 指针移动顺序确保先移动指针再更新窗口数据。错误的顺序会导致边界条件处理不当。8.2 结果更新时机根据问题需求选择扩展窗口时更新收缩窗口时更新或者两者都需要8.3 哈希表比较Java中注意使用equals()而不是比较Integer对象// 正确 if (window.get(c).equals(need.get(c))) { valid; } // 错误可能工作但不推荐 if (window.get(c) need.get(c)) { valid; }9. 滑动窗口的变种与应用9.1 固定大小窗口某些问题要求固定大小的窗口这时只需维护窗口大小不变即可。9.2 数值数组问题滑动窗口同样适用于数值数组如求和大于等于某值的最短子数组乘积小于某值的最长子数组9.3 多指针扩展复杂问题可能需要多个指针协同工作形成多个窗口。10. 实战经验总结模板记忆熟练掌握基本模板遇到新问题时能快速套用问题转化将复杂问题转化为窗口滑动条件判断调试技巧打印窗口变化过程帮助理解边界测试特别注意空输入、单字符等边界情况性能优化根据问题特点选择合适的数据结构在实际编码面试中滑动窗口问题非常常见。建议至少练习20道相关题目直到能够不假思索地写出模板代码。记住关键在于理解窗口滑动条件和结果更新时机而不是死记硬背具体实现。 滑动窗口算法详解：原理、实现与应用场景
1. 滑动窗口算法概述滑动窗口算法是一种高效的数组/字符串处理技巧它通过维护一个可变大小的窗口来遍历数据避免了暴力解法中不必要的重复计算。这种算法特别适合解决子数组/子字符串相关的问题比如寻找满足特定条件的最长子串、最短覆盖子串等。核心思想是使用两个指针通常称为左指针left和右指针right来定义窗口的边界。右指针负责扩展窗口左指针负责收缩窗口通过这种滑动的方式遍历整个数据集合。这种方法的优势在于它能够将时间复杂度从暴力解法的O(n²)降低到O(n)因为每个元素最多被访问两次。2. 滑动窗口的基本框架2.1 算法模板代码以下是滑动窗口算法的通用模板适用于大多数相关问题void slidingWindow(String s) { // 用于记录窗口内数据的哈希表 MapCharacter, Integer window new HashMap(); int left 0, right 0; // 初始化窗口边界 while (right s.length()) { // c是将移入窗口的字符 char c s.charAt(right); // 右移窗口 right; // 进行窗口内数据的一系列更新 // ... // 判断左侧窗口是否要收缩 while (window needs shrink) { // d是将移出窗口的字符 char d s.charAt(left); // 左移窗口 left; // 进行窗口内数据的一系列更新 // ... } } }2.2 关键问题解析使用滑动窗口算法时需要明确回答以下三个核心问题何时扩展窗口移动右指针通常是在当前窗口不满足条件时扩展窗口每次扩展后需要更新窗口内的数据统计何时收缩窗口移动左指针当窗口满足特定条件时开始收缩收缩是为了寻找更优解或满足新条件何时更新结果可能在扩展窗口时更新也可能在收缩窗口时更新取决于具体问题的要求3. 最小覆盖子串问题3.1 问题描述LeetCode第76题给定一个字符串S和一个字符串T在S中找到包含T所有字符的最短子串。示例 输入S ADOBECODEBANC, T ABC 输出BANC3.2 解题思路使用两个哈希表分别记录needT中字符的出现次数window当前窗口中包含T字符的出现次数使用valid变量统计窗口中满足need条件的字符数量滑动窗口过程扩展窗口直到包含T所有字符收缩窗口寻找更小的满足条件的子串记录最小子串的起始位置和长度3.3 完整实现代码public String minWindow(String s, String t) { MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); // 初始化need表 for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } int left 0, right 0; int valid 0; // 匹配的字符数 int start 0, len Integer.MAX_VALUE; // 结果记录 while (right s.length()) { char c s.charAt(right); right; // 更新窗口数据 if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } // 判断是否收缩窗口 while (valid need.size()) { // 更新最小子串 if (right - left len) { start left; len right - left; } char d s.charAt(left); left; // 更新窗口数据 if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return len Integer.MAX_VALUE ? : s.substring(start, start len); }4. 字符串排列问题4.1 问题描述LeetCode第567题给定两个字符串s1和s2判断s2是否包含s1的排列。示例 输入s1 ab, s2 eidbaooo 输出true 解释s2包含s1的排列ba4.2 解题思路这实际上是寻找一个固定长度s1长度的窗口窗口内的字符及其频率要与s1完全匹配使用与最小覆盖子串类似的滑动窗口方法当窗口大小等于s1长度时检查是否匹配4.3 完整实现代码public boolean checkInclusion(String s1, String s2) { MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); for (char c : s1.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } int left 0, right 0; int valid 0; while (right s2.length()) { char c s2.charAt(right); right; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } // 保持窗口大小等于s1长度 while (right - left s1.length()) { if (valid need.size()) { return true; } char d s2.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return false; }5. 找所有字母异位词5.1 问题描述LeetCode第438题给定一个字符串s和一个非空字符串p找到s中所有是p的字母异位词的子串返回这些子串的起始索引。示例 输入s cbaebabacd, p abc 输出[0,6] 解释 起始索引0的子串是cba 起始索引6的子串是bac5.2 解题思路这与字符串排列问题非常相似区别在于需要记录所有符合条件的子串起始位置窗口大小固定为p的长度使用列表收集所有满足条件的起始索引5.3 完整实现代码public ListInteger findAnagrams(String s, String p) { MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); ListInteger res new ArrayList(); for (char c : p.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } int left 0, right 0; int valid 0; while (right s.length()) { char c s.charAt(right); right; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } while (right - left p.length()) { if (valid need.size()) { res.add(left); } char d s.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return res; }6. 最长无重复字符子串6.1 问题描述LeetCode第3题给定一个字符串找出不含有重复字符的最长子串的长度。示例 输入abcabcbb 输出3 解释无重复字符的最长子串是abc6.2 解题思路使用滑动窗口维护当前无重复字符的子串当遇到重复字符时收缩窗口记录窗口的最大长度只需要一个哈希表记录字符最后出现的位置6.3 完整实现代码public int lengthOfLongestSubstring(String s) { MapCharacter, Integer window new HashMap(); int left 0, right 0; int res 0; while (right s.length()) { char c s.charAt(right); right; // 更新窗口数据 window.put(c, window.getOrDefault(c, 0) 1); // 当有重复字符时收缩窗口 while (window.get(c) 1) { char d s.charAt(left); left; window.put(d, window.get(d) - 1); } // 更新结果 res Math.max(res, right - left); } return res; }7. 滑动窗口算法优化技巧7.1 哈希表优化对于字符类问题可以使用固定大小的数组代替哈希表int[] need new int[128]; // ASCII码范围 for (char c : t.toCharArray()) { need[c]; }7.2 边界条件处理空字符串输入目标字符串比源字符串长目标字符串包含源字符串没有的字符7.3 复杂度分析时间复杂度O(n)每个元素最多被访问两次空间复杂度O(k)k是字符集大小8. 常见错误与调试技巧8.1 指针移动顺序确保先移动指针再更新窗口数据。错误的顺序会导致边界条件处理不当。8.2 结果更新时机根据问题需求选择扩展窗口时更新收缩窗口时更新或者两者都需要8.3 哈希表比较Java中注意使用equals()而不是比较Integer对象// 正确 if (window.get(c).equals(need.get(c))) { valid; } // 错误可能工作但不推荐 if (window.get(c) need.get(c)) { valid; }9. 滑动窗口的变种与应用9.1 固定大小窗口某些问题要求固定大小的窗口这时只需维护窗口大小不变即可。9.2 数值数组问题滑动窗口同样适用于数值数组如求和大于等于某值的最短子数组乘积小于某值的最长子数组9.3 多指针扩展复杂问题可能需要多个指针协同工作形成多个窗口。10. 实战经验总结模板记忆熟练掌握基本模板遇到新问题时能快速套用问题转化将复杂问题转化为窗口滑动条件判断调试技巧打印窗口变化过程帮助理解边界测试特别注意空输入、单字符等边界情况性能优化根据问题特点选择合适的数据结构在实际编码面试中滑动窗口问题非常常见。建议至少练习20道相关题目直到能够不假思索地写出模板代码。记住关键在于理解窗口滑动条件和结果更新时机而不是死记硬背具体实现。