【数据结构与算法】【算法专题】滑动窗口
【摘要】 常常使用左右指针解决滑动窗口问题滑动窗口代码框架：void slidingWindow(String s) { // 用合适的数据结构记录窗口中的数据 HashMap<Character, Integer> window = new HashMap<>(); int left = 0, right = 0; while (right < s.length()) { ...
常常使用左右指针解决滑动窗口问题
滑动窗口代码框架：
void slidingWindow(String s) {
// 用合适的数据结构记录窗口中的数据
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
System.out.printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (left < right && window needs shrink) {
// d 是将移出窗口的字符
char d = s.charAt(left);
window.put(d, window.get(d) - 1);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}运用滑动窗口算法思考的问题：
1、什么时候应该扩大窗口？
2、什么时候应该缩小窗口？
3、什么时候应该更新答案？
- 使用左右指针维护一个窗口解决：最小覆盖子串问题： https://leetcode.cn/problems/minimum-window-substring/description/
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> window = new HashMap<>();
HashMap<Character, Integer> need = 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;
int right = 0;
int valid = 0;
int start = 0;
int len = Integer.MAX_VALUE;
while(right < s.length()) {
// 1. 增大窗口操作
char c = s.charAt(right);
right ++;
//1.1 进行窗口更新
if(need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) +1);
// 1.2 窗口值跟预期值相等时更新有效值
if (window.get(c).equals(need.get(c))) {
valid ++;
}
}
// 2. 判断是否需要缩小窗口
while (left < right && valid == need.size()) {
// 2.1 更新满足条件的开始位置和长度(最短的时候才更新)
if (right - left < len) {
start = left;
len = right - left;
}
// 2.2 开始缩小窗口
char d = s.charAt(left);
left ++;
// 2.3 更新窗口的值
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
// 如果当前还相等，则在缩小窗口前有效值-1
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}- 使用双指针解决滑窗问题：字符串排列
https://leetcode.cn/problems/permutation-in-string/description/
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
HashMap<Character, Integer> window = new HashMap<>();
HashMap<Character, Integer> need = new HashMap<>();
for(char c: s1.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) +1);
}
int left = 0;
int right = 0;
int valid = 0;
while (right < s2.length()) {
// 增大窗口
char c = s2.charAt(right);
right ++;
// 更新自己的内容
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) +1);
if (window.get(c).equals(need.get(c))) {
valid ++;
}
}
// 缩小窗口,查找符合排列的内容
while (left < right && right - left >= s1.length()) {
char p = s2.charAt(left);
left ++;
if (valid == need.size()){
return true;
}
if (need.containsKey(p)) {
if (window.get(p).equals(need.get(p))) {
valid --;
}
window.put(p, window.getOrDefault(p, 0) -1);
}
}
}
return false;
}
}- 使用过双针针解决滑动窗口的问题：找到字符串中所有字母异位词
https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> window = new HashMap<>();
HashMap<Character, Integer> need = new HashMap<>();
for(char c: p.toCharArray()) {
need.put(c, need.getOrDefault(c,0) + 1);
}
int left = 0;
int right = 0;
int valid = 0;
List<Integer> res = new ArrayList<>();
while (right < s.length()) {
char c = s.charAt(right);
right ++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid ++;
}
}
while (left < right && right - left >= p.length()) {
char c2 = s.charAt(left);
if (valid == need.size()) {
res.add(left);
}
left ++;
if(need.containsKey(c2)) {
if(window.get(c2).equals(need.get(c2))) {
valid --;
}
window.put(c2, window.getOrDefault(c2, 0) -1);
}
}
}
return res;
}
}- 使用双指针解决滑窗问题：无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> window = new HashMap<>();
int left = 0;
int right = 0;
int res = 0;
while (right < s.length()) {
char c= s.charAt(right);
right++;
window.put(c, window.getOrDefault(c,0) + 1);
while(left < right && window.get(c) > 1) {
char c2 = s.charAt(left);
left++;
window.put(c2, window.getOrDefault(c2,0) -1);
}
if(right - left > res) {
res = right - left;
}
}
return res;
}
}其他习题：
package com.huahua.dr.leetcode.string;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class KeyWordStr {
public static void main(String[] args) {
String[] words = {
"abbb","def","bbg"
};
String inputStr = "aabbbgz";
HashMap<String,Integer> xjWord = new HashMap<>();
for (int i = 0; i < words.length; i++) {
String w1 = words[i];
for (int j = 0; j < words.length; j++) {
if (i == j) {
continue;
}
String w2 =words[j];
String common = getCommonStr(w1,w2);
if (!common.isEmpty()) { //相交合并
int index = inputStr.indexOf(common);
if (index != -1) {
xjWord.put(w1,1);
xjWord.put(w2,1);
if (inputStr.substring(index+common.length()).startsWith("<b>")){
inputStr = inputStr.substring(0,index) +"<b>"+common+inputStr.substring(index+common.length()+"<b>".length());
} else if (inputStr.substring(0,index).endsWith("</b>")) {
inputStr = inputStr.substring(0,index-"</b>".length())+common+"</b>"+inputStr.substring(index+common.length());
}else {
inputStr = inputStr.substring(0,index) +"<b>"+common+"</b>"+inputStr.substring(index+common.length());
}
}
}
}
int index = inputStr.indexOf(w1);
if (index != -1 && !xjWord.containsKey(w1)) {
if (inputStr.substring(index+w1.length()).startsWith("<b>")){
inputStr = inputStr.substring(0,index) +"<b>"+w1+inputStr.substring(index+w1.length()+"<b>".length());
} else if (inputStr.substring(0,index).endsWith("</b>")) {
inputStr = inputStr.substring(0,index-"</b>".length())+w1+"</b>"+inputStr.substring(index+w1.length());
}else {
inputStr = inputStr.substring(0,index) +"<b>"+w1+"</b>"+inputStr.substring(index+w1.length());
}
}
}
System.out.println(inputStr);
}
private static String getCommonStr(String w1, String w2){
StringBuilder res = new StringBuilder();
int left = w1.length() -1;
int right = 0;
int size = Math.min(w1.length(), w2.length());
for (int i = 0; i < size; i++) {
if (w2.charAt(right) == w1.charAt(left)) {
res.append(w2.charAt(right));
right++;
left --;
} else {
break;
}
}
if (!res.toString().isEmpty()) {
int index1 = w1.lastIndexOf(res.toString());
return w1.substring(0,index1)+ res +w2.substring(res.length());
}
return res.toString();
}
}
- https://leetcode.cn/problems/max-consecutive-ones-iii/description/?show=1
- https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/?show=1
- https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/?show=1
- https://leetcode.cn/problems/contains-duplicate-ii/description/?show=1
- https://leetcode.cn/problems/contains-duplicate-iii/description/?show=1
- https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/?show=1
- https://leetcode.cn/problems/longest-repeating-character-replacement/description/?show=1
- https://leetcode.cn/problems/subarray-product-less-than-k/description/?show=1
- https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/description/?show=1
- https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/description/?show=1
- https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/description/?show=1
- https://leetcode.cn/problems/2VG8Kg/description/?show=1
- https://leetcode.cn/problems/ZVAVXX/description/?show=1
- https://leetcode.cn/problems/MPnaiL/?show=1
- https://leetcode.cn/problems/VabMRr/?show=1
- https://leetcode.cn/problems/wtcaE1/?show=1
- https://leetcode.cn/problems/M1oyTv/?show=1
- https://leetcode.cn/problems/7WqeDu/?show=1
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）