窗口的思路是存在一个窗口。满足条件，这时候扭转窗口的大小，到不满足条件时，挪动窗口的右边界线
int[] check = new int[size];//左边界int left =0;//右边界int right = 1;//这个时候就曾经初步创立了窗口freq[in.0] = init;//当初开始滑动窗口ans = init;while(right<in.len){ //当窗口不非法 while(check[in.right] is not valid){ //挪动窗口使窗口非法 check[in.(left++)] = !init; } //这个时候窗口非法 check[in.right] = init; ans = better(ans,right-left+1); right++;}rerurn ans;套用公式
3. 无反复字符的最长子串
滑动窗口一道很典型的题。
int[] check = new int[127];//左边界int left =0;//右边界int right = 1;//这个时候就曾经初步创立了窗口freq[s.charAt(0)] = 1;//当初开始滑动窗口ans = 1;while(right<in.length()){ //当窗口不非法 while(check[in.s.charAt(right)] >0){ //挪动窗口使窗口非法 check[s.charAt(left++)]--; } //这个时候窗口非法 check[in.s.charAt(right)]++; ans = Math,max(ans,right-left+1); right++;}rerurn ans;再用公式套用一个比较复杂的题目
30. 串联所有单词的子串
//窗口大小HashSet<String> validSet ; HashSet<String> inValidSet ; public List<Integer> findSubstring(String s, String[] words) { int size = words.length * words[0].length(); int left = 0; int right = size - 1; List<Integer> list = new ArrayList<>(); validSet = new HashSet<>(); inValidSet = new HashSet<>(); while (right < s.length()) { while (right<s.length() && !isValid(s, left, right,words)) { left++; right++; } if (right<s.length()){ list.add(left); left++; right++; } } return list; } private boolean isValid(String s,int left,int right,String[] words) { if (validSet.contains(s.substring(left,right+1))) return true; if (inValidSet.contains(s.substring(left,right+1))) return false; HashMap<String, Integer> map = new HashMap<>(); for (String word : words) { map.put(word, map.getOrDefault(word, 0) + 1); } while (left <= right) { String temp = s.substring(left, left + words[0].length()); Integer freq = map.getOrDefault(temp, 0); if (freq > 0) map.put(temp, freq - 1); else { inValidSet.add(s); return false; } left += words[0].length(); } validSet.add(s); return true; }再比方，咱们再套一道题
187. 反复的DNA序列
这个题目稍为简略
class Solution { public List<String> findRepeatedDnaSequences(String s) { int left = 0; int right = 10; ArrayList<String> resp = new ArrayList<>(); HashMap<String, Integer> map = new HashMap<>(); while (right<=s.length()){ String temp = s.substring(left, right); map.put(temp,map.getOrDefault(temp,0)+1); right++; left++; } for (String k : map.keySet()) { if (map.get(k) > 1) { resp.add(k); } } return resp; }}