滑动窗口

2024-11-26

滑动窗口笔记

简介

**滑动窗口算法主要用于解决某个符合条件的最短/最长数组，是双指针技巧中的一种

如果使用暴力解法的话是这样：

for (int i = 0; i < nums.length; i++) {
    for (int j = i; j < nums.length; j++) {
        // nums[i, j] 是一个子数组
    }
}

遍历每个子数组从而找到符合条件的数组。滑动窗口就是对这个方法的改善。我们使用一左一右两个指针来维护一个窗口，然后不断滑动，在滑动的过程中去更新答案。代码模板如下：

// 滑动窗口算法伪码框架
void slidingWindow(String s) {
    // 用合适的数据结构记录窗口中的数据，根据具体场景变通
    // 比如说，我想记录窗口中元素出现的次数，就用 map
    // 如果我想记录窗口中的元素和，就可以只用一个 int
    Object window = ...
    
    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s[right];
        window.add(c)
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

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

我们通过不断移动right指针扩大窗口，用来寻找符合条件的子串，找到这个字串后，我们再去移动left指针来缩小窗口，缩小窗口就是去优化我们找到的这个字串。当然，这是去寻找最短的思路，具体的目的根据我们更新窗口的操作来决定，还有什么时候更新答案也是根据具体的要求。

EX.最小覆盖字串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

我们利用哈希表来判断我们的窗口是否满足了条件，如果字符出现的次数相同，那么就是满足了条件。一个哈希表表示我们需要满足的目标，另一个哈希表表示我们目前的进度。每满足一个字符的要求我们就把valid++，当valid的大小等于need的大小时，我们就满足了所有字符的要求。

之后我们就需要去优化我们找到的这个字串，看它还能不能更短。当right到达最右边时窗口的大小就无法再增加了，这时就返回我们的结果。

class Solution {
    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()) {
            // c 是将移入窗口的字符
            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;
                }
                // d 是将移出窗口的字符
                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);
    }
}