滑动窗口算法（Sliding Window Algorithm）

一、写在前面

说起滑动窗口这个算法思路，很多人会感到头秃，这个算法技巧的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案，那么如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果这些都是要考虑的问题点。

二、基本示例

力扣的第76题，最小覆盖字串，难度困难

题目

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

思路分析

我们使用滑动窗口算法时，通过使用哈希字典作为滑动窗口，我们可以用O(1)的时间来完成对字符是否在当前的子字符串中的检查。

滑动窗口是数组或者字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即[left,right)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。我们可以使用哈希表将字符存储在当前窗口[left,right)（最初left=right）中。然后我们向右侧滑动索引right，如果它不在表t中，我们会继续滑动 right。直到s[right]已经存在于HashSet中。此时，我们找到的没有重复字符的最长子字符串将会以索引left开头。如果我们对所有的leift这样做，就可以得到答案。

代码

import java.util.HashMap;
import java.util.Map;
/**
 * 滑动窗口模板
 */
public class Solution {
    public static void main(String[] args) {
        String s="ADOBECODEBANC";
        String t="ABC";
        Solution solution = new Solution();
        System.out.println(solution.minWindow(s,t));
    }
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        // 将t对应字符及次数存储到map
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        // valid 变量表示窗⼝中满⾜ need 条件的字符个数；
        // 如果 valid 和 need.size 的⼤⼩相同，则说明窗⼝已满⾜条件，已经完全覆盖了串 T
        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 (need.get(c).equals(window.get(c))){
                    valid++;
                }
            }
            // 判断左侧窗⼝是否要收缩
            while (valid == need.size()) {
                // 在这⾥更新最⼩覆盖⼦串
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                // d 是将移出窗⼝的字符
                char d = s.charAt(left);
                // 左移窗⼝
                left++;
                if (need.containsKey(d)){
                    if (need.get(d).equals(window.get(d))){
                        valid--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }
        // 返回最⼩覆盖⼦串
        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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

文章参考地址：

https://labuladong.gitee.io/algo/2/21/56/