目录一、什么是滑动窗口滑动窗口的核心思想滑动窗口的基本框架二、经典题目实战1. 长度最小的子数组LeetCode 2092. 无重复字符的最长子串LeetCode 33. 最大连续1的个数 IIILeetCode 10044. 将 x 减到 0 的最小操作数LeetCode 16585. 水果成篮LeetCode 9046. 找到字符串中所有字母异位词LeetCode 4387. 串联所有单词的子串LeetCode 308. 最小覆盖子串LeetCode 76三、滑动窗口算法总结滑动窗口的使用场景解题三步走注意事项一、什么是滑动窗口滑动窗口是一种高效的算法技巧专门用于处理连续子数组或子串的相关问题。它通过维护一个可变大小的窗口在数组或字符串上滑动从而避免重复计算将时间复杂度从 O(n²) 优化到 O(n)。滑动窗口的核心思想滑动窗口的本质是双指针的一种特殊形式两个指针left和right共同界定了一个区间[left, right]这个区间就是所谓的窗口。随着指针的移动窗口不断滑动我们只需要关注窗口内数据的变化而不需要每次都从头计算。滑动窗口的基本框架int left 0, right 0; while (right n) { // 1. 右指针移动元素进入窗口扩大窗口 将 nums[right] 加入窗口 // 2. 判断窗口是否需要收缩 while (窗口需要收缩的条件) { // 3. 左指针移动元素移出窗口缩小窗口 将 nums[left] 移出窗口 left; } // 4. 更新结果 更新结果 // 5. 右指针继续前进 right; }二、经典题目实战1. 长度最小的子数组LeetCode 209题目描述给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和 ≥target的长度最小的连续子数组并返回其长度。算法思路维护一个窗口使窗口内元素之和小于target。当窗口内元素之和第一次大于等于target时记录当前窗口长度然后尝试从左侧缩小窗口看看能否在满足条件的情况下获得更短的子数组。class Solution { public int minSubArrayLen(int target, int[] nums) { int n nums.length; int sum 0; int len Integer.MAX_VALUE; for (int left 0, right 0; right n; right) { sum nums[right]; // 进窗口 while (sum target) { // 判断 len Math.min(len, right - left 1); // 更新结果 sum - nums[left]; // 出窗口 } } return len Integer.MAX_VALUE ? 0 : len; } }为什么滑动窗口能优化暴力解法需要枚举所有起点和终点时间复杂度 O(n²)滑动窗口利用窗口内元素和的连续性left和right指针都只向前移动时间复杂度 O(n)2. 无重复字符的最长子串LeetCode 3题目描述给定一个字符串s找出其中不含有重复字符的最长子串的长度。算法思路维护一个窗口保证窗口内所有字符都不重复。使用哈希表记录窗口内字符出现的次数。当右端字符进入窗口后如果该字符出现次数超过 1说明有重复从左侧缩小窗口直到该字符次数恢复为 1。class Solution { public int lengthOfLongestSubstring(String s) { int[] hash new int[128]; // 用数组模拟哈希表 int left 0, right 0; int n s.length(); int ret 0; while (right n) { hash[s.charAt(right)]; // 进入窗口 while (hash[s.charAt(right)] 1) { // 判断是否有重复 hash[s.charAt(left)]--; // 出窗口 } ret Math.max(ret, right - left 1); // 更新结果 right; // 让下一个元素进入窗口 } return ret; } }要点使用长度为 128 的数组代替哈希表性能更好判断条件hash[s.charAt(right)] 1表示当前字符重复每次缩小窗口时左指针移动并将对应字符计数减一3. 最大连续1的个数 IIILeetCode 1004题目描述给定一个二进制数组nums和一个整数k如果可以翻转最多k个 0则返回数组中连续 1 的最大个数。算法思路不要去想具体的翻转操作问题可以转化为求数组中一段最长的连续区间要求这段区间内 0 的个数不超过 k 个。这就是典型的滑动窗口问题。class Solution { public int longestOnes(int[] nums, int k) { int ret 0; int zero 0; // 统计窗口内 0 的个数 for (int left 0, right 0; right nums.length; right) { if (nums[right] 0) { zero; // 进窗口 } while (zero k) { // 判断 if (nums[left] 0) { zero--; // 出窗口 } } ret Math.max(ret, right - left 1); // 更新结果 } return ret; } }关键点不需要真正翻转 0只需统计 0 的个数窗口内 0 的个数 ≤ k 时窗口合法当 0 的个数超过 k 时从左侧收缩窗口4. 将 x 减到 0 的最小操作数LeetCode 1658题目描述每次操作移除数组最左边或最右边的元素并从x中减去该元素的值。求将x恰好减到 0 所需的最小操作数。算法思路题目要求的是数组左端右端两段连续的、和为x的最短数组。可以转化为求数组内一段连续的、和为sum(nums) - x的最长数组。这样就成了熟悉的滑动窗口问题。class Solution { public int minOperations(int[] nums, int x) { int sum 0; for (int a : nums) { sum a; } int target sum - x; // 细节处理如果 target 0不可能实现 if (target 0) { return -1; } int ret -1; int tmp 0; for (int left 0, right 0; right nums.length; right) { tmp nums[right]; // 进窗口 while (tmp target) { // 判断 tmp - nums[left]; // 出窗口 } if (tmp target) { // 更新结果 ret Math.max(ret, right - left 1); } } return ret -1 ? -1 : nums.length - ret; } }转化思路原问题求两端连续子数组和为 x 的最短长度转化后求中间连续子数组和为sum - x的最长长度最终结果 总长度 - 中间子数组最长长度5. 水果成篮LeetCode 904题目描述你有两个篮子每个篮子只能装单一类型的水果。从任意一棵树开始采摘每棵树摘一个水果一旦遇到不符合篮子中水果类型的树就停止。求最多能采摘多少棵树的果实。算法思路问题等价于求一段最长的连续区间使得区间内水果的种类不超过 2 种。使用滑动窗口配合哈希表来统计窗口内水果种类。class Solution { public int totalFruit(int[] fruits) { int n fruits.length; int[] hash new int[n 1]; // 统计窗口内水果种类及数量 int ret 0; int kinds 0; // 窗口内水果种类数 for (int left 0, right 0; right n; right) { if (hash[fruits[right]] 0) { kinds; // 新种类出现 } hash[fruits[right]]; // 进窗口 while (kinds 2) { // 判断 hash[fruits[left]]--; // 出窗口 if (hash[fruits[left]] 0) { kinds--; // 该种类完全移除 } left; } ret Math.max(ret, right - left 1); // 更新结果 } return ret; } }优化技巧使用数组模拟哈希表比HashMap性能更好额外维护kinds变量记录当前窗口内水果种类数避免每次都遍历哈希表6. 找到字符串中所有字母异位词LeetCode 438题目描述给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。算法思路异位词的长度与p相同因此在s中维护一个长度固定的滑动窗口长度等于p.length()比较窗口内字符计数与p的字符计数是否一致。class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger ret new ArrayList(); int[] hash1 new int[26]; // 统计 p 中字符 int[] hash2 new int[26]; // 统计窗口内字符 for (char ch : p.toCharArray()) { hash1[ch - a]; } int m p.length(); for (int left 0, right 0, count 0; right s.length(); right) { char in s.charAt(right); hash2[in - a]; // 进窗口 // 如果当前字符在 p 中且窗口内该字符数量不超过 p 中的数量 if (hash2[in - a] hash1[in - a]) { count; } // 窗口长度超过 m 时需要收缩 if (right - left 1 m) { char out s.charAt(left); if (hash2[out - a] hash1[out - a]) { count--; } hash2[out - a]--; // 出窗口 left; } // 有效字符计数等于 p 的长度说明找到了异位词 if (count m) { ret.add(left); } } return ret; } }关键优化使用count变量记录窗口内有效字符数即在 p 中出现且数量未超标的字符当count m时说明窗口内字符与 p 完全匹配7. 串联所有单词的子串LeetCode 30题目描述给定一个字符串s和一个字符串数组words找出s中所有包含words中所有单词每个单词只出现一次的串联子串的起始索引。算法思路将每个单词看作一个整体问题就变成了找到字符串中所有字母异位词的升级版。区别在于这里处理的单位是单词而不是字符。class Solution { public ListInteger findSubstring(String s, String[] words) { ListInteger ret new ArrayList(); // 保存字典中所有单词的频次 MapString, Integer hash1 new HashMap(); for (String str : words) { hash1.put(str, hash1.getOrDefault(str, 0) 1); } int len words[0].length(); // 每个单词的长度 int m words.length; // 单词个数 // 需要执行 len 次因为起始位置偏移不同 for (int i 0; i len; i) { MapString, Integer hash2 new HashMap(); for (int left i, right i, count 0; right len s.length(); right len) { // 进窗口 String in s.substring(right, right len); hash2.put(in, hash2.getOrDefault(in, 0) 1); if (hash2.get(in) hash1.getOrDefault(in, 0)) { count; } // 判断窗口是否超出范围 if (right - left 1 len * m) { String out s.substring(left, left len); if (hash2.get(out) hash1.getOrDefault(out, 0)) { count--; } hash2.put(out, hash2.get(out) - 1); left len; } // 更新结果 if (count m) { ret.add(left); } } } return ret; } }注意点需要执行len次滑动窗口因为起始位置可以是0, 1, ..., len-1每次移动步长为len一个单词的长度使用count变量记录有效单词数避免每次遍历哈希表8. 最小覆盖子串LeetCode 76题目描述给你一个字符串s和一个字符串t返回s中涵盖t所有字符的最小子串。算法思路维护一个滑动窗口当窗口内包含了t中所有字符时尝试从左侧缩小窗口以获得更短的子串。使用两个哈希表分别统计目标串和窗口内字符。class Solution { public String minWindow(String s, String t) { int[] hash1 new int[128]; // 统计 t 中字符 int[] hash2 new int[128]; // 统计窗口内字符 // 统计 t 中每个字符出现的次数 for (char ch : t.toCharArray()) { hash1[ch]; } int kinds 0; // t 中不同字符的种类数 for (int count : hash1) { if (count 0) kinds; } int minLen Integer.MAX_VALUE; int begin -1; // 记录最小子串的起始位置 for (int left 0, right 0, count 0; right s.length(); right) { char in s.charAt(right); hash2[in]; // 进窗口 // 如果当前字符在 t 中且窗口内该字符数量达到 t 中的数量 if (hash2[in] hash1[in]) { count; } // 当窗口包含 t 中所有字符时尝试缩小窗口 while (count kinds) { // 更新结果 if (right - left 1 minLen) { minLen right - left 1; begin left; } char out s.charAt(left); if (hash2[out] hash1[out]) { count--; } hash2[out]--; // 出窗口 left; } } return begin -1 ? : s.substring(begin, begin minLen); } }核心难点如何高效判断窗口是否包含t中所有字符使用count变量记录已满足条件的字符种类数当count kinds时说明所有字符都已满足缩小窗口时需要小心维护count的正确性三、滑动窗口算法总结题目窗口特征判断条件结果更新时机长度最小的子数组窗口和≥target窗口和≥target时收缩每次满足条件时无重复字符的最长子串窗口内无重复字符出现重复时收缩每次调整后最大连续1的个数III窗口内0的个数≤k0的个数k时收缩每次调整后将x减到0的最小操作数窗口和target窗口和target时收缩窗口和target时水果成篮窗口内种类≤2种类2时收缩每次调整后字母异位词固定长度窗口长度超限时收缩有效字符数m时串联所有单词固定长度窗口长度超限时收缩有效单词数m时最小覆盖子串窗口覆盖所有字符完全覆盖时收缩每次完全覆盖时滑动窗口的使用场景连续子数组/子串问题研究的对象是一段连续的区间具有单调性窗口扩大时条件更容易满足窗口缩小时条件更难满足需要高效统计避免重复计算利用之前窗口的计算结果解题三步走进窗口右指针移动将新元素纳入窗口判断出窗口检查窗口是否满足条件不满足时移动左指针收缩窗口更新结果根据题目要求在合适的时机更新答案注意事项窗口的左右边界通常是左闭右开或左闭右闭需要统一约定使用数组模拟哈希表比HashMap性能更好适用于字符等有限范围善用count等辅助变量避免每次遍历哈希表判断条件注意边界条件如数组为空、目标值不存在等情况