跳至主要內容

滑动窗口

滑动窗口算法主要用来解决子数组问题，比如寻找符合某个条件的最长/最短子数组。

适用场景

滑动窗口适用于满足以下条件的问题：

  • 数据是线性结构（数组或字符串），需要遍历连续区间
  • 窗口具有单调性——当右边界扩展使窗口"不合法"时，左边界只需单向收缩即可恢复合法性
  • 目标是求最长/最短子数组、子串计数或覆盖性条件

典型信号：题目要求找连续子数组/子串，且暴力枚举所有子区间的时间复杂度为 O(n^2)。如果窗口不满足单调性（例如收缩后可能再次变合法又变不合法），应考虑其他方法（如前缀和 + 哈希表）。

核心框架

算法框架

滑动窗口算法思路：维护一个窗口，不断滑动然后更新答案。

// 滑动窗口算法伪码框架
void slidingWindow(String s) {
    // 用合适的数据结构记录窗口中的数据
    Object window = ...;
    
    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        window.add(c);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            window.remove(d);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

为什么是 O(N)

指针 left, right 不会回退（值只增不减），所以每个元素只会进入窗口一次，然后被移出一次，不会多次进入和离开。

四类经典问题

1. 最小覆盖子串

LeetCode 76「最小覆盖子串」，在 S 中找到包含 T 中全部字母的最短子串。

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, 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);
}

2. 字符串排列

LeetCode 567「字符串的排列」，判断 S 中是否存在包含 T 所有字符且不包含其他字符的子串。

public boolean checkInclusion(String t, String s) {
    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;
    
    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++;
        }

        // 窗口长度等于 t.length() 时收缩
        while (right - left >= t.length()) {
            if (valid == need.size())
                return true;
            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 false;
}

3. 找所有字母异位词

LeetCode 438「找到字符串中所有字母异位词」，返回 S 中所有 T 的排列的起始索引。

public List<Integer> findAnagrams(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;
    List<Integer> res = new ArrayList<>();
    
    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 >= t.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;
}

4. 最长无重复子串

LeetCode 3「无重复字符的最长子串」，找出不含重复字符的最长子串长度。

public int lengthOfLongestSubstring(String s) {
    Map<Character, 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;
}

解题思路

滑动窗口 = 扩大窗口（探索） + 收缩窗口（优化），答案通常在收缩阶段更新。

解题三问

遇到滑动窗口问题，先回答三个问题：

问题回答
何时扩大窗口？右边指针右移，加入新元素
何时收缩窗口？满足某个条件时开始收缩
何时更新答案？收缩过程中或收缩完成后

常见错误

窗口收缩条件写反

最常见的 bug 是把 while 收缩条件写成 if，或者把 > 写成 >=。以最长无重复子串为例：

// 错误：用 if 代替 while，遇到连续重复字符时只收缩一次
if (window.get(c) > 1) { ... }

// 正确：用 while 确保收缩到无重复
while (window.get(c) > 1) { ... }

更新答案的位置错误

答案应该在窗口合法时更新，而不是在扩大窗口后立即更新。常见错误是在 right++ 之后直接更新答案，此时窗口可能已经不满足条件。

// 错误：扩大窗口后立即更新，此时窗口可能包含重复字符
right++;
res = Math.max(res, right - left);  // 窗口可能不合法

// 正确：在收缩完成后再更新
while (window.get(c) > 1) { /* 收缩 */ }
res = Math.max(res, right - left);  // 窗口已保证合法

忘记处理空字符串或空目标

边界情况：当输入为空字符串，或目标字符串 t 为空时，需要提前返回。滑动窗口框架假设至少有一个元素，空输入会导致逻辑异常。