滑动窗口题集

LeetCode76

​ 维护一个滑动窗口，需要判断窗口中是否含有目标串所有字符。如何快速判断该窗口中是否含有目标串所有字符呢？可以使用一个哈希表记录目标串中的各个字符数，并使用一个变量记录目标串中的字符种类。当该变量为0时说明当前窗口包含目标串中所有字符。

​ 使用指针i，j分别表示窗口的右指针和左指针，右指针每向右移动一次，都要判断左指针能否向右移动，从而使子串最短。判断方法为：用一个哈希表记录此时窗口中含有的各个字符数，当前左指针表示的字符数是否大于目标串需要的字符数，如果大于说明左指针可以移动。

实现代码：

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
class Solution {
    public String minWindow(String s, String t) {
        char str[] = s.toCharArray();
        char tstr[] = t.toCharArray();
        int n = str.length;
        int need[] = new int[60];
        int window[] = new int[60];
        int cntNeed = 0;

        for(int i = 0; i < tstr.length; i ++){
            need[getIdx(tstr[i])] ++;
            if(need[getIdx(tstr[i])] == 1)cntNeed++;
        }

        String res = "";
        for(int i = 0, j = 0; i < n; i ++){
            char c = str[i];
            int idx1 = getIdx(c);
    
            if(++window[idx1] == need[idx1]){
                cntNeed --;
            }
            //z
            while(j < i){
                int idx2 = getIdx(str[j]);
                if(window[idx2] > need[idx2]){
                    j ++;
                    window[idx2] --;
                }
                else break;
            }
            if(cntNeed == 0 && (res.length() == 0 || res.length() > i - j + 1))res = s.substring(j,i + 1);
        }
        return res;
    }

    public int getIdx(char c){
        if('A' <= c && c <= 'Z')return c - 'A' + 26;
        else return c - 'a'; 
    }
}