算法-滑动窗口 发表于 2021-03-30 | 更新于 2021-08-29 | 分类于 数据结构与算法-排序专题.基础介绍.滑动窗口.dp专题.数学.树/图/bfs/dfs. 从解决问题的种类,到实际应用中的变形进行总结 1. 滑动窗口1.1 应用场景 一般要求是连续的子串或子数组 1.2 实例 窗口长度不固定 窗口长度固定 1.2.1 无重复字符的最长子串1234567891011121314151617181920212223class 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 串联所有单词的子串123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class 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); } } }}