算法【Java】 —— 滑动窗口

滑动窗口算法详解

滑动窗口算法是一种常用的技术，广泛应用于数组或字符串的子序列问题解决上。其核心思想是通过一个动态的窗口来维护当前考虑的范围，从而优化时间复杂度。与暴力破解的 O(n^2) 时间复杂度相比，滑动窗口通常能将复杂度降低到 O(n)，这是算法设计中的重要思路之一。

滑动窗口的原理

滑动窗口的基本概念是：用两个指针来表示窗口的起始和结束位置。窗口的大小可以根据具体问题而定，通常是动态调整。当你操作窗口时，窗口的起始位置（左指针）或结束位置（右指针）会在迭代过程中移动，从而达到扩展或收缩窗口的目的。

应用示例

以下是使用滑动窗口解决字符串中查找最小长度子串的问题。假设我们需要在字符串 S 中找到包含所有字符 T 的最小窗口子串。

题目描述

给定一个字符串 S 和一个字符串 T，请你在字符串 S 中找出包含 T 所有字符的最小的子串。如果不存在这样的子串，则返回空字符串。

示例

输入:

S = "ADOBECODEBANC"
T = "ABC"

输出:

"BANC"

Java 实现

以下是一个基于滑动窗口的 Java 实现示例：

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {

    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";

        // 频率统计
        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : t.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }

        int required = dictT.size(); // T 中不同字符的数量
        int l = 0, r = 0, formed = 0;

        Map<Character, Integer> windowCounts = new HashMap<>();
        int[] ans = {-1, 0, 0}; // [长度, 左指针, 右指针]

        while (r < s.length()) {
            char c = s.charAt(r);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);

            // 只有当窗口内的字符数量和 T 中字符数量匹配时才形成
            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }

            // 如果已经形成了一个有效的窗口
            while (l <= r && formed == required) {
                c = s.charAt(l);

                // 记录下当前窗口的最小值
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                // 试图将左指针右移以缩小窗口
                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }

                l++;
            }
            r++;
        }

        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }

    public static void main(String[] args) {
        MinimumWindowSubstring solution = new MinimumWindowSubstring();
        String S = "ADOBECODEBANC";
        String T = "ABC";
        System.out.println("最小窗口子串是: " + solution.minWindow(S, T)); // 输出: BANC
    }
}

代码解析

1. 频率统计：首先，我们需要统计字符串 T 中每个字符的出现频率，并记录不同字符的数量。
2. 双指针组合：使用左右指针（l 和 r）来代表当前窗口的左右边界。
3. 窗口扩展与收缩：向右扩展窗口，直到窗口内的字符数量能够满足 T 中的所有字符。然后尝试向左收缩窗口，尽量减少窗口大小，同时保持这些字符依然满足条件。
4. 结果筛选：在每一个符合条件的窗口时，检查并更新记录的最小窗口信息。

总结

滑动窗口是一种高效的算法思想，能够显著提高解决某些特定问题的效率。在实际编程中，合理使用滑动窗口可以大幅度降低时间复杂度，尤其是在处理字符串和数组中的子序列问题时，非常值得开发者掌握和应用。