滑动窗口伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void slidingWindow(String s){
    HashMap<int,char> map;
    int left=0; int right=0;
    while(right<s.length){
        // 将该字符移入窗口
        char c=s[right];
        right++; //增大窗口
        // 进行窗口内数据的一系列更新
    	...
            
         // 判断左侧窗口是否要收缩
    	while (window needs shrink) {
    		// d 是将移出窗口的字符
    		char d = s[left];
        	// 缩小窗口
        	left++;
        	// 进行窗口内数据的一系列更新
        	...
    	}
    } 
}

例：力扣第 76 题最小覆盖子串

思路：

  1. 初始化左右指针left=right=0; 把[left,right) 左闭右开，作为窗口
  2. 不断增大right指针，直到窗口中的字符串符合要求（包含T中所有字符），停止增加right ——>寻找可行解
  3. 增大left指针，缩小窗口，直到窗口的字符串不再符合要求（不包含T中所有字符），停止增加left –>这个可行解的最优解
  4. 重复第2第3步，直到right到达字符串的尽头 –>最优解

HashMap中记录窗口中的字符和需要凑齐的字符

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
class Solution {
    public String minWindow(String s, String t) {
        int left=0;int right=0;
        // 记录目标字符串，每个字符及对应需要的个数
        HashMap<Character,Integer> need=new HashMap<Character,Integer>();
        HashMap<Character,Integer> window=new HashMap<Character,Integer>();
        for(int i=0;i<t.length();i++){
            if(need.get(t.charAt(i))==null){
                need.put(t.charAt(i),1);
                window.put(t.charAt(i),0);
            }else{
                need.put(t.charAt(i),need.get(t.charAt(i))+1);
            }
        }
        int valid=0;//窗口需要满足的字符个数
        int start=0;int end=s.length()+1;  // 记录最优字符的起始位置
        while(right<s.length()){
            char c= s.charAt(right); //加入窗口
             right++;  //扩大窗口
            if(need.containsKey(c)){
                window.put(c,window.get(c)+1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            while(valid==need.size()){ 
                // 寻找可行解的最优解
                if(end-start>right-left){
                    start=left;
                    end=right;
                }
                char d=s.charAt(left); //移除窗口
                left++;  //缩小窗口
                if(window.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return end-start==s.length()+1?"":s.substring(start,end);
    }
}

注意一个点：

Integer的比较最好不要使用==，使用equals()

java 语言处理字符串还是有点麻烦的，一直使用charAt(i) 没有使用索引s[i]方便

同类型练习题

力扣第 567 题「 字符串的排列」 维护的滑动窗口定长

力扣第 438 题「 找到字符串中所有字母异位词」

力扣第 3 题「 无重复字符的最长子串」

209. 长度最小的子数组

2537. 统计好子数组的数目

713. 乘积小于 K 的子数组

3. 无重复字符的最长子串

V getOrDefault(key,defaultValue) 获取某个key的值，如果不存在，设置默认值
V merge(key,value,remappingFunction) 如果key对应的value不存在，则返回该value值；如果存在，则返回通过remappingFunction重新计算后的值。 
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
class Solution {
    /**
    用一个哈希表 cnt 统计窗口内每个元素的出现次数。
    枚举子数组右端点right，那么答案增加了cnt[nums[right]]；然后看左端点 left 最大可以是多少，如果去掉左端点，答案没有小于 k，就可以移动左端点。
    由于左端点及其左边的都可以是好子数组的左端点，所以每个右端点对应的答案个数为left+1。
     */
    public long countGood(int[] nums, int k) {
         HashMap<Integer,Integer> cnt=new HashMap<Integer,Integer>();
        long ans=0;
        int res=0;
        int left=0;
        // 枚举右端点
        for(int right=0;right<nums.length;right++){
            // 加入到滑动窗口
            res+=cnt.getOrDefault(nums[right],0);
            cnt.merge(nums[right], 1, Integer::sum);
            
            // 看是否可以缩小窗口
            while((res-cnt.get(nums[left])+1)>=k){  // 需要缩小窗口
                res-= cnt.merge(nums[left], -1, Integer::sum);;
                left++;
            }
            if(res>=k){
                ans+=left+1;
            }

        }
        return ans;
    }
}