滑动窗口算法线性时间解决区间问题的利器在算法解题中我们经常会遇到一类连续区间相关的问题比如找最长无重复子串、最小覆盖子串、和为目标值的最短子数组等。如果用暴力枚举的方式这类问题的时间复杂度往往是O(n2)O(n^2)O(n2)在数据量较大时会直接超时。而滑动窗口算法作为一种经典的双指针技巧能将这类问题的时间复杂度优化到O(n)O(n)O(n)成为解决连续区间问题的最优解之一。本文将基于滑动窗口的核心思想结合经典例题拆解算法流程让你彻底掌握这一高效算法。一、滑动窗口的核心思想滑动窗口顾名思义就是在数组/字符串上维护一个连续的区间窗口通过动态调整窗口的左右边界在遍历一次数据的过程中找到问题的解。1. 窗口的两种形态滑动窗口的窗口边界通常由两个指针维护left左边界和right右边界窗口区间一般为左闭右开或左闭右闭根据题目调整核心一致。2. 核心操作滑动窗口的核心是先扩大右边界再收缩左边界整个过程遵循以下三步进窗口将右指针指向的元素加入窗口更新窗口内的统计信息如字符频次、元素和等判断检查当前窗口是否满足题目要求的条件如无重复字符、包含目标所有字符、和≥目标值等出窗口若窗口满足条件尝试收缩左边界以优化结果如找最短区间同时更新窗口统计信息更新结果在窗口满足条件的阶段持续记录最优解如最小长度、最大长度。3. 算法优势滑动窗口的左右指针均只向一个方向移动不会回退整个过程仅遍历一次数据因此时间复杂度稳定为O(n)O(n)O(n)nnn为数组/字符串长度空间复杂度通常为O(1)O(1)O(1)或O(k)O(k)O(k)kkk为字符集大小/常数。二、滑动窗口的适用场景滑动窗口主要适用于一维连续区间问题且问题满足单调性即窗口扩大/收缩时满足条件的状态会呈现连续的变化。典型适用场景包括找满足条件的最短连续子数组/子串找满足条件的最长连续子数组/子串找包含目标所有元素的最小覆盖子串统计满足条件的连续子数组/子串数量处理固定长度的滑动窗口统计问题。三、经典例题拆解从基础到进阶结合实际例题拆解滑动窗口的实现流程从基础到进阶让你逐步掌握算法的灵活运用。所有例题均提供Java 实现代码核心逻辑通用可轻松转化为C/Python等语言。例题1长度最小的子数组基础找最短满足条件区间题目链接LeetCode 209. 长度最小的子数组题目描述给定一个含有nnn个正整数的数组和一个正整数target找出该数组中满足其和 ≥target的长度最小的连续子数组返回其长度若不存在返回 0。核心思路维护窗口和sum右指针不断扩大窗口将元素加入sum当sum ≥ target时窗口满足条件开始收缩左边界同时更新最小窗口长度收缩左边界时将左指针指向的元素从sum中减去直到sum target。实现代码class Solution { public int minSubArrayLen(int target, int[] nums) { int n nums.length; int sum 0; // 窗口内元素和 int minLen Integer.MAX_VALUE; // 最小窗口长度 // 左闭右闭窗口[left, right] for (int left 0, right 0; right n; right) { sum nums[right]; // 进窗口 // 满足条件收缩左边界 while (sum target) { minLen Math.min(minLen, right - left 1); // 更新结果 sum - nums[left]; // 出窗口 } } return minLen Integer.MAX_VALUE ? 0 : minLen; } }关键要点这是动态窗口的基础模型右边界负责扩大左边界负责优化while循环收缩左边界确保找到以当前右边界为结尾的最短满足条件窗口。例题2无重复字符的最长子串基础找最长满足条件区间题目链接LeetCode 3. 无重复字符的最长子串题目描述给定一个字符串s找出其中不含有重复字符的最长子串的长度。核心思路用数组hash模拟哈希表统计窗口内字符的频次右指针扩大窗口若当前字符频次1说明窗口内有重复收缩左边界直到频次1每次窗口无重复时更新最长窗口长度。实现代码class Solution { public int lengthOfLongestSubstring(String s) { char[] arr s.toCharArray(); int[] hash new int[128]; // 覆盖ASCII字符集 int maxLen 0; for (int left 0, right 0; right arr.length; right) { hash[arr[right]]; // 进窗口 // 有重复字符收缩左边界 while (hash[arr[right]] 1) { hash[arr[left]]--; // 出窗口 } maxLen Math.max(maxLen, right - left 1); // 更新结果 } return maxLen; } }关键要点哈希表是滑动窗口的常用工具用于统计窗口内元素/字符的状态本题需保证窗口始终满足无重复因此收缩左边界是为了恢复窗口的有效性。例题3最大连续1的个数 III进阶允许有限次修改题目链接LeetCode 1004. 最大连续1的个数 III题目描述给定一个二进制数组nums和一个整数k可以翻转最多k个 0 为 1返回数组中连续 1 的最大个数。核心思路将问题转化为找最长的连续区间其中 0 的个数 ≤k用变量zero统计窗口内 0 的个数右指针扩大窗口若zero k收缩左边界直到zero ≤ k持续更新最长窗口长度。实现代码class Solution { public int longestOnes(int[] nums, int k) { int maxLen 0; int zero 0; // 窗口内0的个数 for (int left 0, right 0; right nums.length; right) { if (nums[right] 0) zero; // 进窗口统计0 // 0的个数超标收缩左边界 while (zero k) { if (nums[left] 0) zero--; // 出窗口减少0 } maxLen Math.max(maxLen, right - left 1); // 更新结果 } return maxLen; } }关键要点本题的核心是问题转化将“翻转0”转化为“统计0的个数”降低问题复杂度滑动窗口可灵活处理有限次修改/替换的区间问题只需统计修改次数即可。例题4最小覆盖子串高频面试题覆盖目标所有元素题目链接LeetCode 76. 最小覆盖子串题目描述给你一个字符串s、一个字符串t返回s中涵盖t所有字符的最小子串若不存在返回空字符串。注意t中重复字符子串中该字符数量需不少于t中数量。核心思路用两个数组hash1统计t的字符频次、hash2统计窗口字符频次kinds记录t中不同字符的种类count记录窗口中匹配t的字符种类右指针扩大窗口若当前字符的hash2频次等于hash1频次count当count kinds时窗口覆盖t所有字符收缩左边界优化最小长度收缩左边界时若当前字符的hash2频次等于hash1频次count--表示该字符不再匹配。实现代码class Solution { public String minWindow(String s, String t) { char[] sArr s.toCharArray(); char[] tArr t.toCharArray(); int[] hash1 new int[128]; int kinds 0; // t中不同字符的种类 for (char c : tArr) { if (hash1[c] 0) kinds; } int[] hash2 new int[128]; int minLen Integer.MAX_VALUE; int begin -1; // 最小子串起始索引 int count 0; // 窗口中匹配t的字符种类 for (int left 0, right 0; right sArr.length; right) { char in sArr[right]; hash2[in]; // 该字符匹配完成 if (hash2[in] hash1[in]) count; // 窗口覆盖t所有字符收缩左边界 while (count kinds) { // 更新最小子串 if (right - left 1 minLen) { minLen right - left 1; begin left; } char out sArr[left]; // 该字符不再匹配 if (hash2[out] hash1[out]) count--; hash2[out]--; } } return begin -1 ? : s.substring(begin, begin minLen); } }关键要点本题是滑动窗口的经典难题需维护“匹配种类数”而非单纯的频次count变量是核心通过它快速判断窗口是否满足条件避免每次遍历哈希表优化时间效率。例题5水果成篮进阶固定种类数的最长区间题目链接LeetCode 904. 水果成篮题目描述给定一个整数数组fruits表示果树的水果种类只有两个篮子每个篮子只能装一种水果从任意树开始采摘必须连续采摘返回能收集的水果最大数目。核心思路将问题转化为找最长的连续区间其中水果种类数 ≤ 2用数组hash统计窗口内水果频次kinds记录窗口内水果种类右指针扩大窗口若水果首次出现kinds若kinds 2收缩左边界直到kinds ≤ 2频次为0时kinds--更新最长窗口长度。实现代码class Solution { public int totalFruit(int[] fruits) { int n fruits.length; int[] hash new int[n 1]; // 水果种类为数组索引范围匹配 int kinds 0; // 窗口内水果种类 int maxLen 0; for (int left 0, right 0; right n; right) { int in fruits[right]; if (hash[in] 0) kinds; hash[in]; // 进窗口 // 种类数超标收缩左边界 while (kinds 2) { int out fruits[left]; hash[out]--; if (hash[out] 0) kinds--; // 该种类消失 } maxLen Math.max(maxLen, right - left 1); // 更新结果 } return maxLen; } }关键要点本题是固定种类数的区间问题可扩展到“最多k种元素的最长区间”统计种类数时需注意频次为0时及时减少种类数保证统计准确。四、滑动窗口的通用解题模板通过以上例题我们可以总结出滑动窗口的通用模板分为找最短区间和找最长区间两种只需根据题目调整窗口统计信息和满足条件的判断逻辑即可。模板1找满足条件的最短连续区间// 适用于和≥target、最小覆盖子串等 public int slidingWindowShort(int[] nums, int target) { int n nums.length; int res Integer.MAX_VALUE; // 初始化最短结果为最大值 int windowInfo 0; // 窗口统计信息和/频次/种类等 for (int left 0, right 0; right n; right) { windowInfo nums[right]; // 进窗口更新统计信息 // 满足条件收缩左边界优化结果 while (满足条件) { res Math.min(res, right - left 1); // 更新最短结果 windowInfo - nums[left]; // 出窗口更新统计信息 } } return res Integer.MAX_VALUE ? 0 : res; // 无结果返回0 }模板2找满足条件的最长连续区间// 适用于无重复子串、最大连续1的个数、水果成篮等 public int slidingWindowLong(int[] nums, int k) { int n nums.length; int res 0; // 初始化最长结果为0 int windowInfo 0; // 窗口统计信息频次/种类/0的个数等 for (int left 0, right 0; right n; right) { // 进窗口更新统计信息根据题目调整 if (nums[right] 0) windowInfo; // 不满足条件收缩左边界恢复有效性 while (windowInfo k) { if (nums[left] 0) windowInfo--; // 出窗口更新统计信息 } res Math.max(res, right - left 1); // 更新最长结果 } return res; }五、滑动窗口的解题技巧与注意事项1. 核心技巧问题转化将复杂问题转化为“窗口统计信息满足某一条件”的问题如翻转0转化为统计0的个数哈希表/数组统计优先用数组字符集/数值范围固定时模拟哈希表效率更高哈希表用于数值范围不固定的场景双指针同向移动确保左右指针均只移动一次保证时间复杂度为O(n)O(n)O(n)维护关键变量如匹配种类数count、元素个数zero避免重复遍历统计信息优化效率。2. 注意事项窗口边界的定义统一使用左闭右闭/左闭右开避免下标越界初始化值的选择找最短区间时结果初始化为Integer.MAX_VALUE找最长区间时结果初始化为0边界条件处理无满足条件的结果时需返回题目指定的默认值如0、空字符串字符集覆盖处理字符串问题时数组大小设为128ASCII或256扩展ASCII确保覆盖所有字符。六、总结滑动窗口算法是解决一维连续区间问题的“万能钥匙”其核心是通过同向双指针动态调整窗口边界在一次遍历中找到最优解时间复杂度稳定为O(n)O(n)O(n)在面试和算法竞赛中都是高频考点。掌握滑动窗口的关键在于理解**“进窗口→判断→出窗口→更新结果”**的核心流程学会问题转化将复杂问题转化为窗口统计信息的判断熟练使用哈希表/数组维护窗口内的统计信息结合通用模板根据题目灵活调整判断逻辑和统计信息。本文的例题覆盖了滑动窗口的绝大多数适用场景建议大家手动敲写代码理解每一步的逻辑在此基础上做更多的拓展练习如找到字符串中所有字母异位词、和为k的子数组等相信你能彻底掌握这一高效算法