算法-滑动窗口

发表于   |   更新于 | 分类于

从解决问题的种类，到实际应用中的变形进行总结

1. 滑动窗口

1.1 应用场景

image-20210628151653188

一般要求是连续的子串或子数组

1.2 实例

  • 窗口长度不固定
  • 窗口长度固定

1.2.1 无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLongestSubstring(String s) {
		if(s.length() == 0) return 0;
        //1.定义窗口边界
        int start = 0;
        int end = 0;
        //2.定义窗口状态！！
        //小技巧：如果求最长，定义为0，如果求最小，则定义为一个超过整体长度的值
        int max = 0;
        Map<Character,Integer> m = new HashMap<>();
        //3.挪动窗口
        for(end; end<s.length(); ++end){
            //每次窗口状态改变都进行判断，是否满足要求，这里就是判断此时进来的字符是不是重复的
            char c = s.charAt(end);
            if(m.containsKey(c)){
               //修改，让当前窗口满足要求
                start = Math.max(start, m.get(c)+1);
            }
            max = Math.max(max, end-start+1);
            m.put(c,end);
        }
    }
}

1.2.1 串联所有单词的子串

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
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> l = new ArrayList<>();
        if(s.length() == 0) return l;
        //定义窗口边界
        int start = 0;
        int end = 0;
        //定义状态
        //1.存放起始位置的列表已定义
        //2.用于进行状态确认的信息：
        //2.1 定义一个Map代表需要查找的词组,并初始化
        Map<String,Integer> m = new HashMap<>();
        for(String word: words){
            m.put(word, m.getOrDefault(word,0)+1);
        }
        //2.2 定义一些经常使用的变量
        int wordlen = len(words[0]);
        int winlen = len(words) * wordlen;
        //3.进入窗口，分析各窗口状态
        for(int start=0; start<s.length(); ++start){
            //分析窗口状态
            int attempt = 0;
            boolean matchFailed = false;
            Map<String,Integer> wordTimes = new HashMap<>();		
            //窗口内遍历
   			while(attempt<start+winlen){
                String tempWord = s.subString(attempt:attempt+wordlen);
                if(!m.containsKey(tempWord)){
                    matchFailed = true;
                    break;
                }else{
                    wordTimes.put(tempWord,getOrDefault(tempWord,0)+1);
                    if(wordTimes.get(tempWord)>m.get(tempWord)){
                        matchFailed = true;
                        break;
                    }
                    attempt = attemp+wordlen;
                }
            } 
            if(matchFailed){
                continue;
            }
            if(wordTimes.equals(m)){
                l.add(start);
            }
        }
    }
}