滑动窗口算法框架总结_滑动窗口计数框架

一、滑动窗口算法

也会使用两个指针，但和双指针算法不同的是双指针算法关注的往往是两个指针正在指向的两个元素，而滑动窗口算法关注的是两个指针之间的窗口，动态维护窗口中的信息。

滑动窗口算法一般用于解决子串或子数组问题，碰到这两种问题可以优先考虑滑动窗口。

二、四个例子

leetcode 209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

假如使用暴力求解：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int minLen = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; ++i){
            int sum = 0;
            for(int j = i; j < nums.length; ++j){
                sum += nums[j];
                if(sum >= s){
                    minLen = Math.min(minLen, j-i+1);
                    break;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

每次从第 i 个元素开始向后累加，直到子数组和大于等于 s，然后更新最小长度。
时间复杂度为 $O(n^2)$。

使用滑动窗口求解：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int winSum = 0;
        while(right < nums.length){
            winSum += nums[right];
            right++;
            while(winSum >= s){
                minLen = Math.min(minLen, right-left);
                winSum -= nums[left];
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

窗口中维护一个 窗口子数组和 的信息（winSum），窗口每向右纳入一个新元素（right 指针右移），就检查窗口的合法性，如果窗口合法，则更新最小窗口信息，并不断从左边移除窗口内的元素（left 指针右移），并同时检查窗口合法性和更新最小窗口信息，直到窗口不合法。此时，再不断向右纳入新元素，直至窗口重新合法或算法结束。
时间复杂度为 $O(n)$。

暴力解法每个元素都会被累加若干次，而滑动窗口每个元素至多累加累减一次，避免了大量的冗余计算。

如果我们理解了上述过程，就可以总结出滑动窗口算法的伪码框架：

while(right < nums.length){
    window.add(nums[right]);
    right++;
    while(window 合法){ // 如果窗口合法，移动 left 缩小窗口
        result = update(window); // 根据当前窗口，更新结果
        window.remove(nums[left]);
        left++;
    }
}
return result;
1
2
3
4
5
6
7
8
9
10

leetcode 30. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：
输入：
s = “barfoothefoobarman”,
words = [“foo”,“bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：
输入：
s = “wordgoodgoodgoodbestword”,
words = [“word”,“good”,“best”,“word”]
输出：[]

滑动窗口解法：

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if(s.length() == 0 || words.length == 0) return result;
        Map<String, Integer> countMap = new HashMap<>();
        for(String w : words) countMap.put(w, countMap.getOrDefault(w, 0)+1);
        
        Map<String, Integer> workMap = new HashMap<>(); // 维护窗口中的单词
        int wordLen = words[0].length();
        int wordsLen = words.length*wordLen;
        for(int i = 0; i < wordLen; ++i){ // 错位遍历，保证所有情况都遍历到
        	workMap.clear();
            int left = i, right = i;
            while(right <= s.length()-wordLen){
                String rw = s.substring(right, right+wordLen);
                workMap.put(rw, workMap.getOrDefault(rw, 0)+1);
                right += wordLen;
                if(!countMap.containsKey(rw)){ // 重置窗口
                    left = right;
                    workMap.clear();
                    continue;
                }
                while(workMap.get(rw) > countMap.get(rw)){ // 删除左边单词，使窗口合法
                    String lw = s.substring(left, left+wordLen);
                    workMap.put(lw, workMap.get(lw)-1);
                    left += wordLen;
                }
                if(right-left == wordsLen) result.add(left);
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

对应的滑动窗口伪码框架为：

while(right 没有越界){
	window.add(rightWord);
	right 右移;
	if(window 不合法 && 不能通过移动 left 使 window 合法){
		重置窗口;
		continue;
	}
	while(window 不合法){
		window.remove(leftWord);
		left 右移;
	}
	if(window 符合要求) result = update(window);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

每次先往窗口里添加一个新单词，通过 HashMap 判断添加的单词是否合法，如果新单词根本不在 words 里面，那当前窗口就全部不可用了，重置窗口，将 left 设为 right，重新匹配。如果新单词在 words 里，但新单词在窗口里的出现次数大于在 words 里的出现次数，通过移动 left 指针，不断删除窗口左端的单词，直至窗口重新合法，如果 words 里的所有单词都在窗口中，就可以更新结果集了。

和上一个例子不同的是，这里 left 右移是为了使窗口重新合法，而上一个例子是为了使窗口重新不合法，所以两者结果集的更新时机不同。

leetcode 438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

• 字母异位词指字母相同，但排列不同的字符串。
• 不考虑答案输出的顺序。

示例 1:
输入:
s: “cbaebabacd” p: “abc”
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

示例 2:
输入:
s: “abab” p: “ab”
输出:
[0, 1, 2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。

滑动窗口解法：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if(s.length() == 0) return result;
        int[] map = new int[26];
        for(char c : p.toCharArray()) ++map[c-'a'];

        char[] ss = s.toCharArray();
        int[] workMap = new int[26];
        int left = 0, right = 0;
        while(right < ss.length){
            int rc = ss[right]-'a';
            ++workMap[rc];
            right++;
            if(map[rc] == 0){ // 重置窗口
                while(left < right) --workMap[ss[left++]-'a']; // 移除窗口中的全部元素
                continue;
            }
            while(workMap[rc] > map[rc]){ // 重新使窗口合法
                --workMap[ss[left]-'a'];
                left++;
            }
            if(right-left == p.length()) result.add(left);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

这个例子和上一个很相似，只是基本单元不同，上一个例子的基本单元是字符串，而这个是字符。

为什么不像上一个例子一样，直接调用 Arrays.fill(map, 0) 来重置窗口呢？
因为对上一个例子来说字符串的 substring()、hashCode() 和 equals() 操作比较费时，不如直接 clear()。而这个例子相对来说直接 Arrays.fill() 更费时，因为会重置许多无关元素。

leetcode 76. 最小覆盖子串

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

示例：
输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”

说明：

• 如果 S 中不存这样的子串，则返回空字符串 “”。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

滑动窗口解法：

class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for(char c : t.toCharArray()) ++map[c];
        
        char[] ss = s.toCharArray();
        int start = -1, len = Integer.MAX_VALUE;
        int left = 0, right = 0, count = 0;
        while(right < ss.length){
            if(map[ss[right]]-- > 0) ++count; // count 用来统计在窗口中的有效字符
            right++;
            while(count == t.length()){ // 移动 left 使窗口重新不合法
                if(right-left < len){ // 更新结果
                    len = right-left;
                    start = left;
                }
                if(++map[ss[left]] > 0) --count;
                left++;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

只用到了一个 map，空间利用率很高，只是稍微难理解一点。
map 本来只用于统计 t 字符串，但这里在窗口滑动的过程中直接修改了 map 的计数。我们可以将 if(map[ss[right]]-- > 0) ++count; 简单理解为把 map 中的 t 的有效字符借到窗口中来，if(++map[ss[left]] > 0) --count; 理解为把 t 的有效字符从窗口中还回 map。

最小覆盖子串问题其实是一种子串包含问题的泛化，前面的 串联所有单词的子串 和 找到字符串中所有字母异位词 都属于这种子串包含问题。我们同样可以只用一个 map 来解决。
串联所有单词的子串：

class Solution {
	public List<Integer> findSubstring(String s, String[] words) {
		List<Integer> result = new ArrayList<>();
		if(s.length() == 0 || words.length == 0) return result;
        Map<String, Integer> countMap = new HashMap<>();
		int wordLen = words[0].length();
		int wordsLen = words.length*wordLen;
		for(int i = 0; i < wordLen; ++i){ // 错位遍历，保证所有情况都遍历到
            countMap.clear();
            for(String w : words) countMap.put(w, countMap.getOrDefault(w, 0)+1);
			int left = i, right = i, count = 0, val;
			while(right+wordLen <= s.length()){
                String rw = s.substring(right, right+wordLen);
                countMap.put(rw, (val = countMap.getOrDefault(rw, 0))-1);
                if(val > 0) ++count; // 有效单词被放入窗口
                right += wordLen;
                while(count == words.length){
                    if(right-left == wordsLen) result.add(left);
                    String lw = s.substring(left, left+wordLen);
                    countMap.put(lw, val = countMap.get(lw)+1);
                    if(val > 0) --count; // 有效单词被移出窗口
                    left += wordLen;
                }
			}
		}
		return result;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

找到字符串中所有字母异位词：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if(s.length() == 0) return result;
        int[] map = new int[26];
        for(char c : p.toCharArray()) ++map[c-'a'];

        char[] ss = s.toCharArray();
        int left = 0, right = 0, count = 0;
        while(right < ss.length){
            if(map[ss[right]-'a']-- > 0) ++count;
            right++;
            while(count == p.length()){ // 重新使窗口不合法
                if(right-left == count) result.add(left);
                if(++map[ss[left]-'a'] > 0) --count;
                left++;
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、滑动窗口算法框架

通过上面四道题，我们可以总结出常见的滑动窗口算法框架：

int left = 0, right = 0;

while(right < s.length){
    window.add(s[right]);
    right++;
    
    while(valid){
        window.remove(s[left]);
        left++;
    }
}
1
2
3
4
5
6
7
8
9
10
11

其中 window 维护的数据类型视题目而定，可能就是一个变量也可能是一个哈希表或数组。

稍微麻烦的地方就是这个 valid 条件，为了实现这个条件的实时更新，我们可能会写很多代码。比如前面的题目，看起来解法篇幅那么长，实际上思想还是很简单，只是大多数代码都在处理这个问题而已。

部分参考：
https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%8A%80%E5%B7%A7.md