滑动窗⼝算法总结（附经典题⽬）6.滑动窗⼝
求满⾜⼀定条件的 连续⼦区间，⼦串⼀般⽤滑动窗⼝
模板
public slidingWindow(String s, String t){
HashMap<Character,Integer> need,window;
for(char c: t.toCharArray()){
need.put(OrDefault(c,0)+1);
}
int left right valid=0;
while(right<s.length()){
//当前字符
char CharAt(right);
//增⼤右窗⼝
right++;
//进⾏窗⼝内数据的更新
...
//判断左窗⼝是够需要收缩
while(window needs shrink){
char d=t.charAt(left);
left++;
//进⾏窗⼝数据的更新
...
}
}
}
最后返回原字符串的[left,right)
题⽬：长度最⼩的⼦数组
解法：
我们以该题为例
我们依次增⼤右边界，直到满⾜条件后，增⼤左边界缩⼩区间，直到不满⾜条件后再次增⼤右边界......
时间复杂度O（N）
public int minSubArrayLen(int target, int[] nums) { if(nums.length==0){
return 0;
}
int left=0;
int right=0;
int sum=0;
int result=Integer.MAX_VALUE;
//通常主循环是以右边界为判断条件
while(right<nums.length){
sum=sum+nums[right];
//满⾜条件后开始增⼤左边界
while(sum>=target){
result=Math.min(result,right-left+1);
sum=sum-nums[left];
left++;
}
right++;
}
/
/ 如果没有满⾜条件的区间，返回0
return result==Integer.MAX_VALUE? 0:result;
}
题⽬：⽆重复字符最长⼦串
解法：
public int lengthOfLongestSubstring(String s) {
if(s.length()==0){
return 0;
}
//存储已经访问过的字符
HashMap<Character,Integer> hashMap=new HashMap<>();
int right=0;
int left=0;
int result=Integer.MIN_VALUE;
while (right < s.length()) {
char c=s.charAt(right);
right++;
hashMap.put(OrDefault(c,0)+1);
//左边界更新
//这⾥要⽤equals，因为Integer类型⽐较的是地址（如果是[-127，128]内的数字，由于缓存存在，地址相同，此时equals和==⽆区别，但超过这个范围地址就不同了）
(c).equals(2)){
char b=s.charAt(left);
left++;
hashMap.put((b)-1);
}
result=Math.max(right-left,result);
}
return result;
}
题⽬：字符串排列
解法
public boolean checkInclusion(String s1, String s2) {
HashMap<Character,Integer> need=new HashMap<>();
HashMap<Character,Integer> window=new HashMap<>();
int right=0;
int left=0;
int valid=0;
for(char c: s1.toCharArray()){
need.put(OrDefault(c,0)+1);
}
while(right<s2.length()){
char c=s2.charAt(right);
right++;
ainsKey(c)){
window.put(OrDefault(c,0)+1);
(c).(c))){
valid++;
}
}
while(valid==need.size()){
if(right-left==s1.length()){
return true;
}
char b=s2.charAt(left);
left++;
if (ainsKey(b)) {
(b).(b))){
valid--;
}
window.put(OrDefault(b,0)-1);
}
}
}
return fal;
}
题⽬：找到字符串中所有字母异位词
解法：
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result=new ArrayList<>();
HashMap<Character,Integer> need=new HashMap<>();
HashMap<Character,Integer> window=new HashMap<>();
for(char CharArray()){
need.put(OrDefault(c,0)+1);
}
int right=0;
int left=0;
int valid=0;
while(right<s.length()){
char c=s.charAt(right);
right++;
ainsKey(c)){
window.put(OrDefault(c,0)+1);
(c).(c))){
valid++;
}
}
//开始收缩左边界
while(valid==need.size()){
if(right-left==p.length()){
result.add(left);
}
char b=s.charAt(left);
left++;
ainsKey(b)){
//如果当前数⽬刚好够，减⼀次就不够了
(b).(b))){
valid--;
}
window.put(OrDefault(b,0)-1);
}
}
}
return result;
}
题⽬：最⼩覆盖⼦串
