窗口的思路是存在一个窗口。满足条件，这时候改变窗口的大小，到不满足条件时，移动窗口的左边界限
int[] check = new int[size];
//左边界
int left =0;
//右边界
int right = 1;
//这个时候就已经初步创建了窗口
freq[in.0] = init;
//现在开始滑动窗口
ans = init;
while(right套用公式
3. 无重复字符的最长子串
滑动窗口一道很典型的题。
int[] check = new int[127];
//左边界
int left =0;
//右边界
int right = 1;
//这个时候就已经初步创建了窗口
freq[s.charAt(0)] = 1;
//现在开始滑动窗口
ans = 1;
while(right0){
//移动窗口使窗口合法
check[s.charAt(left++)]--;
}
//这个时候窗口合法
check[in.s.charAt(right)]++;
ans = Math,max(ans,right-left+1);
right++;
}
rerurn ans;
再用公式套用一个比较复杂的题目
30. 串联所有单词的子串
//窗口大小
HashSet validSet ;
HashSet inValidSet ;
public List findSubstring(String s, String[] words) {
int size = words.length * words[0].length();
int left = 0;
int right = size - 1;
List list = new ArrayList<>();
validSet = new HashSet<>();
inValidSet = new HashSet<>();
while (right < s.length()) {
while (right 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;
} 【2021.12.19刷题笔记--滑动窗口系列】再比如，我们再套一道题
187. 重复的DNA序列
这个题目稍为简单
class Solution {
public List findRepeatedDnaSequences(String s) {
int left = 0;
int right = 10;
ArrayList resp = new ArrayList<>();
HashMap 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;
}
}推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔