基本数据结构---滑动窗口
滑动窗口前言一、应用场景二、模板三、实践76. 最小覆盖子串567. 字符串的排列438. 找到字符串中所有字母异位词3. 无重复字符的最长子串总结前言滑动窗口属于双指针技巧的其中一种，两外两种分别是左右指针和快慢指针。其基本思想是维护一个窗口，不断滑动，更新数据，找到满足题意的答案。一、应用场景滑动窗口常用来解决字符串的匹配问题。匹配问题套路：不满足题意，右移窗口，更新数据；满足题意，左移窗口，
·
前言
滑动窗口属于双指针技巧的其中一种，两外两种分别是左右指针和快慢指针。其基本思想是维护一个窗口，不断滑动，更新数据，找到满足题意的答案。
一、应用场景
滑动窗口常用来解决字符串的匹配问题。
匹配问题套路：不满足题意，右移窗口，更新数据；满足题意，左移窗口，更新数据。
其他情况需要具体问题，具体分析，如3.无重复字符的最长字串。
二、模板
public String minWindow(String s, String t) {
//need 是匹配字符串t的哈希表
HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
//将匹配字符串t更新到哈希表need中
for (int i = 0; i < t.length(); i++) {
need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
}
int left = 0, right = 0; //window的左右边界，左闭右开原则[left,right)
int valid = 0; //字符和数量都一至，valid才+1
//不满足题意，右移滑动窗口
while (right < s.length()) {
char c = s.charAt(right++); // c 是将移⼊窗⼝的字符 right++ 是右移窗口
// 进⾏窗⼝内数据的⼀系列更新...
// 判断左侧窗⼝是否要收缩
while (满足题意，左移窗口，并在合适的位置更新结果){
char d = s.charAt(left++); // d 是将移出窗⼝的字符 left++ 是左移窗⼝
// 进⾏窗⼝内数据的⼀系列更新 ...
}
}
}
三、实践
76. 最小覆盖子串
不满足题意，窗口右移，满足题意，窗口左移
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
}
int left = 0, right = 0, valid = 0;
int start = 0, len = Integer.MAX_VALUE; // 记录最⼩覆盖⼦串的起始索引及⻓度
while (right < s.length()) {
char c = s.charAt(right++); // c 是将移⼊窗⼝的字符 右移窗口
// 进⾏窗⼝内数据的⼀系列更新
if (need.containsKey(c)) {
//window只记录在t中的字符
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 判断左侧窗⼝是否要收缩 满足题意时收缩
while (valid == need.size()) {
//更新结果数据
if (right - left < len) {
start = left;
len = right - left;
if (len == t.length()) {
break;
}
}
char d = s.charAt(left++); // d 是将移出窗⼝的字符 左移窗口
// 进⾏窗⼝内数据的⼀系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len); // 返回最⼩覆盖⼦串
}
567. 字符串的排列
public boolean checkInclusion(String s1, String s2) {
HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (int i = 0; i < s1.length(); i++) {
need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while (right < s2.length()) {
char c = s2.charAt(right++); // c 是将移⼊窗⼝的字符 右移窗口
// 进⾏窗⼝内数据的⼀系列更新
if (need.containsKey(c)) {
//window只记录在s1中的字符
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 判断左侧窗⼝是否要收缩 满足题意时收缩
while (valid == need.size()) {
//更新结果数据
if (right - left == s1.length()) {
return true; // 记录结果
}
char d = s2.charAt(left++); // d 是将移出窗⼝的字符 左移窗口
// 进⾏窗⼝内数据的⼀系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
return false;
}
438. 找到字符串中所有字母异位词
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (int i = 0; i < p.length(); i++) {
need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
ArrayList<Integer> list = new ArrayList<>(); // 记录结果
while (right < s.length()) {
char c = s.charAt(right++); // c 是将移⼊窗⼝的字符 右移窗口
// 进⾏窗⼝内数据的⼀系列更新
if (need.containsKey(c)) {
//window只记录在p中的字符
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
while (valid == need.size()) {
//更新结果数据
if (right - left == p.length()) {
list.add(left);
}
char d = s.charAt(left++); // d 是将移出窗⼝的字符 左移窗口
// 进⾏窗⼝内数据的⼀系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return list;
}
3. 无重复字符的最长子串
非字符串匹配问题，需要用到滑动窗口。满足题意窗口右移，不满足题意停止然后左移，待重新满足题意时更新结果数据。
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int len = 0; // 记录结果
while (right < s.length()) {
char c = s.charAt(right++);
// 进⾏窗⼝内数据的⼀系列更新
window.put(c, window.getOrDefault(c, 0) + 1);
while (window.get(c) > 1) {
char d = s.charAt(left++);
// 进⾏窗⼝内数据的⼀系列更新
window.put(d, window.getOrDefault(d, 0) - 1);
}
if (len < right - left) {
len = right - left; // 在这⾥更新答案
}
}
return len;
}
239. 滑动窗口最大值
需要频繁判断最值时用堆很方便，不需要每次都进行删除操作，当更新结果数据时更新堆数据
public int[] maxSlidingWindow(int[] nums, int k) {
//大根堆存储num和其index
PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
}
});
int left = 0, right = 0;
int[] res = new int[nums.length - k + 1]; //总共有length-k+1个最大值
int index = 0;
while (right < nums.length) {
int num = nums[right++]; //窗口右移
heap.add(new int[]{num, right - 1}); //更新数据
if (right - left == k) { //满足题意时收缩窗口
while (heap.peek()[1] < left) { //删除堆中无效数据（不在滑动窗口中的数据）
heap.poll();
}
res[index++] = heap.peek()[0]; //更新结果
left++; //窗口左移
}
}
return res;
}
总结
滑动窗口常用来解决字符串的匹配问题。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)