窗口的思路是存在一个窗口。满足条件，这时候扭转窗口的大小，到不满足条件时，挪动窗口的右边界线
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;
}
}