滑动窗口算法详解

MrHe··3 min read

滑动窗口是双指针技巧的一种应用，用于解决数组/链表子区间问题。它可以将暴力解法的 O(n²) 优化到 O(n)。

滑动窗口通过维护一个动态的窗口区间，来避免不必要的重复计算。这个窗口就像一个"滑块"一样在数组上移动，每次移动只关注窗口内外的变化，而不是重新计算整个窗口。

经典题型：最小覆盖子串

给你一个字符串 S、一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

方法一：暴力解法

最容易想到的就是遍历所有可能的子串，检查每个子串是否包含 T 的所有字符，然后找出最短的。

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
        return "";
    }

    Map<Character, Integer> targetCount = new HashMap<>();
    for (char c : t.toCharArray()) {
        targetCount.put(c, targetCount.getOrDefault(c, 0) + 1);
    }

    int minLength = Integer.MAX_VALUE;
    String result = "";

    for (int i = 0; i < s.length(); i++) {
        for (int j = i + t.length(); j <= s.length(); j++) {
            String sub = s.substring(i, j);
            if (isValid(sub, targetCount)) {
                if (sub.length() < minLength) {
                    minLength = sub.length();
                    result = sub;
                }
            }
        }
    }

    return result;
}

private boolean isValid(String s, Map<Character, Integer> targetCount) {
    Map<Character, Integer> windowCount = new HashMap<>();
    for (char c : s.toCharArray()) {
        if (targetCount.containsKey(c)) {
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
        }
    }

    for (Map.Entry<Character, Integer> entry : targetCount.entrySet()) {
        if (windowCount.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
            return false;
        }
    }

    return true;
}

这个解法的时间复杂度是 O(n³)，因为遍历子串是 O(n²)，验证每个子串需要 O(n)。

方法二：滑动窗口（标准解法）

使用滑动窗口来优化，我们维护一个窗口 [left, right]，不断扩大右边界，直到窗口包含所有 T 的字符。然后尝试缩小左边界，找到满足条件的最小窗口。

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
        return "";
    }

    // 统计 T 中每个字符的出现次数
    Map<Character, Integer> targetCount = new HashMap<>();
    for (char c : t.toCharArray()) {
        targetCount.put(c, targetCount.getOrDefault(c, 0) + 1);
    }

    // 维护窗口中已匹配的字符数量
    int formed = 0;
    int required = targetCount.size();

    // 窗口的左右边界
    int left = 0, right = 0;

    // 保存最小窗口的信息
    int minLength = Integer.MAX_VALUE;
    String result = "";

    // 当前窗口中字符的计数
    Map<Character, Integer> windowCount = new HashMap<>();

    while (right < s.length()) {
        // 扩大窗口，加入 right 处的字符
        char c = s.charAt(right);
        windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);

        // 如果加入的字符是 T 中的，并且数量已经达到 T 中的数量，formed 加一
        if (targetCount.containsKey(c) && windowCount.get(c).intValue() == targetCount.get(c).intValue()) {
            formed++;
        }

        // 如果当前窗口已经包含了所有 T 的字符，尝试缩小窗口
        while (left <= right && formed == required) {
            // 更新最小窗口
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                result = s.substring(left, right + 1);
            }

            // 移出 left 处的字符
            char leftChar = s.charAt(left);
            windowCount.put(leftChar, windowCount.get(leftChar) - 1);

            // 如果移出的字符导致不再满足条件，formed 减一
            if (targetCount.containsKey(leftChar) && windowCount.get(leftChar) < targetCount.get(leftChar)) {
                formed--;
            }

            // 缩小窗口
            left++;
        }

        // 扩大窗口
        right++;
    }

    return result;
}

这个解法的时间复杂度是 O(n)，因为每个元素最多被访问两次（一次通过 right 指针，一次通过 left 指针）。

方法三：优化后的滑动窗口

我们可以对方法二做一些优化，比如过滤掉不需要的字符，以及使用数组代替哈希表来提高效率。

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
        return "";
    }

    // 使用数组代替哈希表，因为字符范围是 ASCII
    int[] targetCount = new int[128];
    for (char c : t.toCharArray()) {
        targetCount[c]++;
    }

    // 统计还需要匹配的字符总数
    int remaining = t.length();

    // 窗口的左右边界
    int left = 0, right = 0;

    // 保存最小窗口的信息
    int minLength = Integer.MAX_VALUE;
    int start = 0;

    // 过滤掉不在 t 中的字符，只处理在 t 中出现的字符
    while (right < s.length()) {
        char rightChar = s.charAt(right);

        // 如果 rightChar 在 t 中
        if (targetCount[rightChar] > 0) {
            remaining--;
        }

        targetCount[rightChar]--;

        // 如果当前窗口已经包含了所有 T 的字符，尝试缩小窗口
        while (remaining == 0) {
            // 更新最小窗口
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                start = left;
            }

            // 移出 left 处的字符
            char leftChar = s.charAt(left);
            targetCount[leftChar]++;

            // 如果移出的字符导致不再满足条件
            if (targetCount[leftChar] > 0) {
                remaining++;
            }

            // 缩小窗口
            left++;
        }

        // 扩大窗口
        right++;
    }

    return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);
}

这个解法的时间复杂度仍然是 O(n)，但由于使用了数组代替哈希表，常数因子更小，实际运行更快。

滑动窗口的应用场景

滑动窗口适用于解决以下问题：

  1. 寻找满足某个条件的最长子数组/子串

  2. 寻找满足某个条件的最短子数组/子串

  3. 统计某个条件下的子数组/子串数量

  4. 计算数组中所有长度为 k 的子数组的某种特性

滑动窗口的解题模板

public void slidingWindowTemplate(String[] args) {
    // 1. 初始化窗口左右边界
    int left = 0, right = 0;

    // 2. 初始化结果变量
    int result = 0;

    // 3. 初始化窗口状态的变量（如哈希表、计数器等）
    Map<Character, Integer> window = new HashMap<>();

    while (right < array.length) {
        // 4. 扩大窗口，更新窗口状态
        window.put(array[right], window.getOrDefault(array[right], 0) + 1);
        right++;

        // 5. 判断是否需要缩小窗口
        while (shouldShrink(window)) {
            // 6. 更新结果（在缩小窗口前）
            result = Math.max(result, right - left);

            // 7. 缩小窗口，更新窗口状态
            window.put(array[left], window.get(array[left]) - 1);
            left++;
        }
    }

    return result;
}

滑动窗口是算法中非常重要的一种思想，掌握好它对于解决很多字符串和数组问题都有帮助。在实际面试中，如果能想到用滑动窗口解决一个问题，通常意味着你已经找到了最优解。

  • #5rur5yqo56qx5yj