滑动窗口算法总结

滑动窗口概念

滑动窗口是一种解决数组（或字符串）的子序列问题的通用方法，特别适合处理连续子数组或子串的问题。它通过维护一个可变大小的"窗口"，在线性时间内解决原本需要嵌套循环的问题，从而将时间复杂度从O(n²)降低到O(n)。

基本思想：

维护一个"窗口"，这个窗口包含了当前正在考虑的元素序列
窗口有两个边界：左边界(left)和右边界(right)
通过移动这两个边界来"滑动"窗口，从而遍历所有可能的子序列

滑动窗口的工作方式：

初始化左右指针，通常都指向序列的开始位置
右指针向右移动，扩大窗口，直到窗口满足某个条件
当条件满足时，记录结果，然后左指针向右移动，缩小窗口，直到条件不再满足（用while循环）
重复步骤2和3，直到右指针到达序列末尾

滑动窗口的适用场景

滑动窗口算法特别适合解决以下类型的问题：

寻找满足特定条件的连续子数组或子串
- 最大/最小长度的子数组，其和为k
- 不含重复字符的最长子串
- 包含特定字符的最短子串
需要在线性时间内解决的子序列问题
- 固定大小窗口的最大/最小值
- 满足特定条件的变长窗口
需要维护窗口内元素某种状态的问题
- 窗口内的最大/最小值
- 窗口内的元素种类数
- 窗口内元素的频率统计

滑动窗口的类型

1. 固定大小的滑动窗口

窗口大小固定不变
适用于求解固定长度子数组的问题

2. 可变大小的滑动窗口

窗口大小根据条件动态调整
适用于求解满足特定条件的最长/最短子数组

滑动窗口算法模板

固定窗口大小的模板：

public void slidingWindowFixed(int[] nums, int k) {
    int n = nums.length;
    // 初始化窗口
    for (int i = 0; i < k; i++) {
        // 处理窗口内的元素
    }
    
    // 滑动窗口
    for (int i = k; i < n; i++) {
        // 添加新元素
        // 移除旧元素
        // 处理当前窗口
    }
}

可变窗口大小的模板：

public void slidingWindowVariable(int[] nums) {
    int left = 0;
    int right = 0;
    int n = nums.length;
    
    while (right < n) {
        // 扩大窗口
        // 更新窗口内的状态
        
        while (/* 窗口需要收缩的条件 */) {
            // 缩小窗口
            // 更新窗口内的状态
            left++;
        }
        
        // 更新结果
        right++;
    }
}

滑动窗口的应用实例

例1：无重复字符的最长子串

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

思路：使用滑动窗口和HashSet记录窗口中的字符。

public int lengthOfLongestSubstring(String s) {
    HashSet<Character> set = new HashSet<>();
    int maxLength = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(s.charAt(right));
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

例2：长度为K的子数组最大和

问题：给定一个整数数组和一个整数k，找出长度为k的连续子数组的最大和。

思路：使用固定大小的滑动窗口。

public int maxSumSubarray(int[] nums, int k) {
    int n = nums.length;
    int maxSum = 0;
    int windowSum = 0;
    
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }
    maxSum = windowSum;
    
    // 滑动窗口
    for (int i = k; i < n; i++) {
        windowSum = windowSum + nums[i] - nums[i - k]; // 添加新元素，移除旧元素
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

例3：最小覆盖子串

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

思路：使用可变大小的滑动窗口和HashMap记录窗口中字符的频率。

public String minWindow(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>();
    HashMap<Character, Integer> window = new HashMap<>();
    
    // 统计t中字符的频率
    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);
}

例4：找到所有字母异位词

问题：给定两个字符串s和p，找到s中所有p的异位词的起始索引。异位词指字母相同，但排列不同的字符串。

思路：使用固定大小的滑动窗口和数组记录字符频率。

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s == null || s.length() == 0 || p == null || p.length() == 0) {
        return result;
    }
    
    int[] charCount = new int[26]; // 假设只有小写字母
    
    // 统计p中字符的频率
    for (char c : p.toCharArray()) {
        charCount[c - 'a']++;
    }
    
    int left = 0, right = 0;
    int count = p.length(); // 需要匹配的字符数
    
    while (right < s.length()) {
        // 如果当前字符在p中，减少需要匹配的字符数
        if (charCount[s.charAt(right) - 'a'] > 0) {
            count--;
        }
        // 减少对应字符的计数（可能为负，表示多余的字符）
        charCount[s.charAt(right) - 'a']--;
        right++;
        
        // 当窗口大小等于p的长度时，检查是否找到异位词
        if (right - left == p.length()) {
            if (count == 0) {
                result.add(left);
            }
            
            // 恢复左指针对应的字符计数
            if (charCount[s.charAt(left) - 'a'] >= 0) {
                count++;
            }
            charCount[s.charAt(left) - 'a']++;
            left++;
        }
    }
    
    return result;
}

滑动窗口算法的优化技巧

使用合适的数据结构：
- 使用HashSet/HashMap快速判断元素是否存在
- 使用双端队列(Deque)维护窗口内的最大/最小值
避免不必要的计算：
- 增量更新窗口状态，而不是每次重新计算
- 记录关键状态（如有效字符数量）避免重复检查
直接跳跃：
- 在某些情况下，可以直接将左指针跳到特定位置，而不是一步步移动

滑动窗口与其他算法的结合

滑动窗口算法常常与其他技术结合使用：

哈希表：用于快速查找和频率统计
双指针：滑动窗口本身就是双指针的一种特殊形式
前缀和：结合前缀和可以快速计算窗口内的元素和
单调队列：用于在O(1)时间内获取窗口内的最大/最小值

总结

滑动窗口是一种强大的算法技巧，它通过巧妙地维护和更新窗口状态，将许多原本需要O(n²)时间的子数组问题优化到O(n)时间。掌握滑动窗口技巧，对于解决数组、字符串的连续子序列问题非常有帮助。

关键要点：

识别问题是否适合使用滑动窗口
确定窗口的扩张和收缩条件
正确维护窗口内的状态
在适当的时机更新结果