在一个长度为 100 万的数组中找出连续 k 个元素的最大和。最直观的思路是：对每个可能的起始位置，累加 k 个元素，记录最大值。这需要大约 100 万次循环，每次循环内部还要遍历 k 个元素——总的时间复杂度是 $O(n \times k)$。

但如果换一种思路：先计算前 k 个元素的和，然后每次只减去最左边的元素、加上新进入窗口的元素。这样每个元素只需要处理一次，时间复杂度直接降到 $O(n)$。

这就是滑动窗口算法的核心魅力：用两个指针维护一个"窗口"，在遍历过程中动态调整窗口大小，将原本需要嵌套循环的问题优化为单次扫描。

滑动窗口的本质与适用场景

滑动窗口（Sliding Window）是一种专门处理连续子数组或子字符串问题的算法技巧。它通过维护一个由左右指针定义的窗口，在遍历过程中根据特定条件扩大或缩小窗口，从而高效地找到满足条件的解。

这种方法能够成立的关键在于：窗口内的元素只增不减地被处理。每个元素最多进入窗口一次、离开窗口一次，因此即使代码中存在嵌套的 while 循环，整体时间复杂度仍然是 $O(n)$。

滑动窗口算法在网络协议领域有着悠久的历史。TCP 协议中的流量控制机制就采用了滑动窗口的思想——发送方维护一个窗口，窗口内的数据可以连续发送而不必等待确认，当收到确认后窗口向前滑动。这种机制有效解决了网络延迟对传输效率的影响，使得数据传输的吞吐量不再受限于往返时延。

滑动窗口协议示意图

图片来源: Wikipedia - Sliding Window Protocol

在算法领域，滑动窗口主要适用于以下几类问题：

  • 在数组或字符串中寻找满足特定条件的最长子数组/子串
  • 在数组或字符串中寻找满足特定条件的最短子数组/子串
  • 计算满足特定条件的子数组/子串个数
  • 对固定大小的窗口进行统计（最大值、平均值、异位词检测等）

判断一个问题是否适合滑动窗口，关键在于：问题是否涉及连续区间，以及是否能够通过增量更新来避免重复计算。

两大类型：固定窗口与可变窗口

滑动窗口问题根据窗口大小是否固定，可以分为两大类型。理解这两种类型的差异，是掌握滑动窗口算法的第一步。

固定长度滑动窗口

固定窗口的大小在整个过程中保持不变，窗口每次向右移动一格，移出一个元素、加入一个元素。这类问题通常要求在每个窗口位置计算某个统计值（最大值、和、平均值等）或判断窗口是否满足特定条件。

经典问题包括：

  • LeetCode 239: 滑动窗口最大值
  • LeetCode 643: 子数组最大平均数
  • LeetCode 438: 找到字符串中所有字母异位词
  • LeetCode 567: 字符串的排列

固定窗口的特点是：右指针每次移动一步，左指针也必须同步移动一步，窗口大小恒定。因此内层的收缩逻辑通常可以简化为单次操作，而非 while 循环。

可变长度滑动窗口

可变窗口的大小根据条件动态调整，通常用于寻找满足特定条件的最优解（最长、最短、个数等）。这类问题需要根据窗口是否满足条件来决定扩大还是缩小窗口。

可变窗口又可以细分为三类：

越短越合法（求最长）：窗口越短越容易满足条件，目标是找到满足条件的最长窗口。典型问题：

  • LeetCode 3: 无重复字符的最长子串
  • LeetCode 904: 水果成篮
  • LeetCode 1004: 最大连续 1 的个数 III
  • LeetCode 424: 替换后的最长重复字符

越长越合法（求最短）：窗口越长越容易满足条件，目标是找到满足条件的最短窗口。典型问题：

  • LeetCode 209: 长度最小的子数组
  • LeetCode 76: 最小覆盖子串

求子数组个数：统计满足条件的子数组数量。典型问题：

  • LeetCode 713: 乘积小于 K 的子数组

核心框架模板

理解了两种类型后，我们来看滑动窗口的核心代码框架。这个框架可以应对绝大多数滑动窗口问题，关键在于根据具体问题填入正确的逻辑。

public void slidingWindow(String s) {
    // 用合适的数据结构记录窗口中的数据
    Map<Character, Integer> window = new HashMap<>();
    
    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        // 更新窗口数据
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 扩大窗口
        right++;
        
        // 判断左侧窗口是否需要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            // 更新窗口数据
            window.put(d, window.get(d) - 1);
            // 缩小窗口
            left++;
        }
    }
}

使用这个框架时，需要回答三个关键问题：

  1. 什么时候扩大窗口？ 右指针移动时，窗口内数据如何更新？
  2. 什么时候缩小窗口？ 满足什么条件时需要移动左指针，窗口内数据如何更新？
  3. 什么时候更新结果？ 在扩大窗口时还是缩小窗口时记录答案？

这三个问题的答案因题而异，但框架本身保持不变。接下来通过具体题目来演示如何应用这个框架。

经典题目详解

固定窗口：LeetCode 239 滑动窗口最大值

这是固定窗口问题中最经典的一道，也是面试高频题。

题目描述：给定一个整数数组 nums 和一个整数 k，请返回滑动窗口中的最大值。滑动窗口每次向右移动一位。

示例：nums = [1,3,-1,-3,5,3,6,7], k = 3，输出 [3,3,5,5,6,7]

解题思路：

暴力解法对每个窗口扫描一遍找最大值，时间复杂度 $O(n \times k)$。但观察一个现象：如果 nums[1] = 3 大于 nums[0] = 1，那么在包含这两个元素的任何窗口中，nums[0] 永远不可能是最大值——它会被 nums[1] “压制”。

基于这个观察，我们可以维护一个单调递减队列，队列中存储元素的下标（而非值）。队列头部始终是当前窗口的最大值下标。当窗口滑动时：

  1. 移除所有超出窗口范围的下标（队头下标小于 i - k + 1）
  2. 移除所有比当前元素小的下标（它们不可能成为最大值）
  3. 将当前元素下标加入队尾
  4. 队头元素就是当前窗口的最大值
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // 存储下标
        
        for (int i = 0; i < n; i++) {
            // 移除超出窗口范围的下标
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // 移除比当前元素小的所有下标（单调递减）
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            // 加入当前下标
            deque.offerLast(i);
            // 记录结果（窗口形成后）
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

复杂度分析：每个元素最多入队一次、出队一次，时间复杂度 $O(n)$；队列最多存储 k 个元素，空间复杂度 $O(k)$。

单调队列工作原理

图片来源: 作者绘制，展示单调队列如何在滑动窗口中维护最大值候选

可变窗口求最长：LeetCode 3 无重复字符的最长子串

这是滑动窗口入门的经典题目，也是面试中出现频率极高的一道题。

题目描述：给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。

示例：s = "abcabcbb"，输出 3（最长无重复子串是 "abc"）

解题思路：

用哈希表记录窗口中每个字符的出现次数。当窗口中加入一个字符后，如果该字符的出现次数超过 1，说明窗口内有重复，需要从左侧不断收缩窗口直到该字符次数降为 1。

这里的关键洞察是：窗口收缩完成后，一定保证无重复，因此应该在这个时刻更新结果。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int maxLen = 0;
        
        while (right < s.length()) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            right++;
            
            // 当出现重复字符时收缩窗口
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                window.put(d, window.get(d) - 1);
                left++;
            }
            
            // 收缩完成后更新结果
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
}

复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(min(m, n))$，其中 m 是字符集大小。

可变窗口求最短：LeetCode 209 长度最小的子数组

这道题展示了滑动窗口的另一面：求满足条件的最短子数组。

题目描述：给定一个正整数数组 nums 和一个正整数 target，找出数组中满足其和 $\geq$ target 的长度最小的连续子数组，返回其长度。如果不存在则返回 0。

示例：nums = [2,3,1,2,4,3], target = 7，输出 2（子数组 [4,3] 的和为 7，长度最小）

解题思路：

与求最长不同，求最短时窗口越长越容易满足条件。因此策略是：先扩大窗口直到满足条件，然后尝试收缩窗口寻找更短的解。

由于数组元素都是正数，窗口扩大时和一定增加，窗口缩小时和一定减少。这保证了单调性，使得我们可以用简单的滑动窗口解决。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLen = n + 1;
        int sum = 0;
        
        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];
                left++;
            }
        }
        
        return minLen <= n ? minLen : 0;
    }
}

复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(1)$。

求子数组个数：LeetCode 713 乘积小于 K 的子数组

这类问题要求统计满足条件的子数组数量，需要一些计数技巧。

题目描述：给定一个正整数数组 nums 和一个整数 k，返回子数组内所有元素的乘积严格小于 k 的连续子数组的个数。

示例：nums = [10,5,2,6], k = 100，输出 8

解题思路：

关键观察：如果子数组 nums[i..j] 的乘积小于 k，那么以 j 结尾的所有子数组 nums[i..j], nums[i+1..j], ..., nums[j..j] 的乘积也都小于 k（因为元素都是正数）。

因此，当窗口 nums[left..right] 的乘积小于 k 时，以 right 结尾的合法子数组个数为 right - left + 1。

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0; // 乘积最小为 1，不可能小于等于 0 的 k
        
        int count = 0;
        int product = 1;
        
        for (int left = 0, right = 0; right < nums.length; right++) {
            product *= nums[right];
            
            // 收缩窗口直到乘积小于 k
            while (product >= k) {
                product /= nums[left];
                left++;
            }
            
            // 以 right 结尾的合法子数组个数
            count += right - left + 1;
        }
        
        return count;
    }
}

复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(1)$。

进阶问题：LeetCode 76 最小覆盖子串

这道题是滑动窗口的集大成者，综合了哈希表、双指针、字符串处理等多个知识点。

题目描述：给定字符串 s 和 t，返回 s 中涵盖 t 所有字符（包括重复字符）的最小子串。如果不存在则返回空字符串。

示例：s = "ADOBECODEBANC", t = "ABC"，输出 "BANC"

解题思路：

需要两个哈希表：need 记录 t 中各字符的需求量，window 记录当前窗口中各字符的数量。引入变量 valid 记录窗口中满足需求的字符种类数。

当 valid == need.size() 时，窗口满足条件，尝试收缩；否则继续扩大窗口。

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, minLen = 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 < minLen) {
                    start = left;
                    minLen = 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 minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

复杂度分析：时间复杂度 $O(|s| + |t|)$，空间复杂度 $O(|字符集|)$。

双约束问题：LeetCode 904 水果成篮

这道题可以抽象为：最长至多包含 2 种不同元素的子数组。

题目描述：给定一个整数数组 fruits，返回可以收集的水果的最大数量。规则是：只有两个篮子，每个篮子只能装一种水果，从任意位置开始，每棵树只能摘一个水果，遇到第三种水果时停止。

示例：fruits = [1,2,1]，输出 3

解题思路：

本质上就是求最长且包含不超过 2 种不同元素的子数组。用哈希表记录窗口中各水果类型的数量，当类型数超过 2 时收缩窗口。

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> basket = new HashMap<>();
        int left = 0, maxFruits = 0;
        
        for (int right = 0; right < fruits.length; right++) {
            basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);
            
            // 当篮子中的水果种类超过 2 种时收缩
            while (basket.size() > 2) {
                basket.put(fruits[left], basket.get(fruits[left]) - 1);
                if (basket.get(fruits[left]) == 0) {
                    basket.remove(fruits[left]);
                }
                left++;
            }
            
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        
        return maxFruits;
    }
}

替换问题：LeetCode 1004 最大连续 1 的个数 III

这类问题允许对窗口内的元素进行有限次数的"修改"，求修改后能形成的最长连续区间。

题目描述：给定一个二进制数组 nums 和一个整数 k，可以翻转最多 k 个 0，返回数组中连续 1 的最大个数。

示例：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2，输出 6

解题思路：

问题转化为：找到一个最长的窗口，窗口内最多包含 k 个 0。用变量记录窗口内 0 的个数，超过 k 时收缩窗口。

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, maxLen = 0;
        int zeroCount = 0;
        
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            
            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

时间复杂度为何是 O(n)

初看滑动窗口代码，很多人会疑惑：明明有嵌套的 while 循环，为什么时间复杂度是 $O(n)$ 而不是 $O(n^2)$？

关键在于指针的单调性。左右指针都只会向前移动，永远不会回退。每个元素最多被加入窗口一次、从窗口移出一次。因此，虽然存在嵌套循环，但总的操作次数仍然是线性级别的。

用摊还分析的角度来看：对于 n 个元素，每个元素被处理有限次（通常是 2 次：一次进入、一次离开），总操作次数是 $O(n)$。

这与暴力解法的嵌套循环有本质区别：暴力解法中内层循环的指针会不断回退，导致同一元素被重复处理多次。

LeetCode 滑动窗口题目清单

以下是按类型整理的 LeetCode 滑动窗口经典题目：

固定长度窗口：

    1. 滑动窗口最大值（单调队列）
    1. 子数组最大平均数
    1. 大小为 K 且平均值大于等于阈值的子数组数目
    1. 找到字符串中所有字母异位词
    1. 字符串的排列
    1. 长度为三且各字符不同的子字符串

可变窗口 - 求最长：

    1. 无重复字符的最长子串
    1. 水果成篮
    1. 最大连续 1 的个数 III
    1. 替换后的最长重复字符

可变窗口 - 求最短：

    1. 长度最小的子数组
    1. 最小覆盖子串

可变窗口 - 求个数：

    1. 乘积小于 K 的子数组

小结

滑动窗口算法的核心价值在于化繁为简：将需要嵌套循环的问题转化为单次遍历。掌握这一算法的关键是理解两种窗口类型的区别，以及框架中三个关键问题的回答方式。

固定窗口的关键是维护窗口内状态的高效更新（如单调队列）；可变窗口的关键是判断何时扩大、何时收缩。无论哪种类型，核心都是利用数据的单调性或特殊结构来避免重复计算。

当你面对一个连续子数组/子串问题时，不妨问自己：能否用两个指针维护一个窗口？窗口状态能否增量更新？如果答案是肯定的，滑动窗口很可能就是最优解。

参考资料