滑动窗口算法总结

滑动窗口概念

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

基本思想:

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

滑动窗口的工作方式:

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

滑动窗口的适用场景

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

  1. 寻找满足特定条件的连续子数组或子串

    • 最大/最小长度的子数组,其和为k
    • 不含重复字符的最长子串
    • 包含特定字符的最短子串
  2. 需要在线性时间内解决的子序列问题

    • 固定大小窗口的最大/最小值
    • 满足特定条件的变长窗口
  3. 需要维护窗口内元素某种状态的问题

    • 窗口内的最大/最小值
    • 窗口内的元素种类数
    • 窗口内元素的频率统计

滑动窗口的类型

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

滑动窗口算法的优化技巧

  1. 使用合适的数据结构

    • 使用HashSet/HashMap快速判断元素是否存在
    • 使用双端队列(Deque)维护窗口内的最大/最小值
  2. 避免不必要的计算

    • 增量更新窗口状态,而不是每次重新计算
    • 记录关键状态(如有效字符数量)避免重复检查
  3. 直接跳跃

    • 在某些情况下,可以直接将左指针跳到特定位置,而不是一步步移动

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

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

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

总结

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

关键要点:

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