滑动窗口:
程序员文章站
2022-03-11 20:00:34
...
滑动窗口:
框架:
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
//自己创建两个有映射关系的数组
//HashMap<Character,Integer> needs = new HashMap<>();
//HashMap<Character,Integer> windows = new HashMap<>();
//可以选择性讲s和t转换成字符串
//,会方便一些,读取好像也会快一点
char[] str1=s.toCharArray();
char[] str2=t.toCharArray();
//保存对应字母的个数
int[] sArr=new int[128];
int[] tArr=new int[128];
//更新窗口
for (char c : str2) tArr[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = str1[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = str1[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
例题:
一、LeetCode 76 题,Minimum Window Substring,难度 Hard,
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
换句话说,第一个字符串的排列之一是第二个字符串的子串。
滑动窗口算法的思路是这样:
***1、***我们在字符串S
中使用双指针中的左右指针技巧,初始化left = right = 0
,把索引左闭右开区间[left, right)
称为一个「窗口」。
***2、***我们先不断地增加right
指针扩大窗口[left, right)
,直到窗口中的字符串符合要求(包含了T
中的所有字符)。
***3、***此时,我们停止增加right
,转而不断增加left
指针缩小窗口[left, right)
,直到窗口中的字符串不再符合要求(不包含T
中的所有字符了)。同时,每次增加left
,我们都要更新一轮结果。
***4、***重复第 2 和第 3 步,直到right
到达字符串S
的尽头。
初始状态:
增加right
,直到窗口[left, right)
包含了T
中所有字符:
现在开始增加left
,缩小窗口[left, right)
。
直到窗口中的字符串不再符合要求,left
不再继续移动。
代码如下:
public static String minWindow(String s, String t){
char[] str1=s.toCharArray();
char[] str2=t.toCharArray();
int[] sArr=new int[128];
int[] tArr=new int[128];
//初始化
int valid=0;
for (int i = 0; i < t.length(); i++) {
tArr[str2[i]]++;
if(tArr[str2[i]]==1){
valid++;
}
}
int left=0,right=0;
int count=0;
int start=0;//保存结果
int len= Integer.MAX_VALUE;
while(right<str1.length){
char ch=str1[right];
right++;
if(tArr[ch]!=0){//包含
sArr[ch]++;
if(sArr[ch]==tArr[ch]){//相同元素且个数相同
count++;
}
}
while (valid==count){
if(right-left<len){//更新结果
len=right-left;
start=left;
}
char temp=str1[left];
left++;
if(tArr[temp]!=0){//同时移动左边界,到窗口不满足条件!
if(sArr[temp]==tArr[temp]){
count--;
}
sArr[temp]--;
}
}
}
return
len==Integer.MAX_VALUE?"":s.substring(start,start+len);
}
二、找所有字母异位词
这是 LeetCode 第 438 题,Find All Anagrams in a String,难度 Medium:
相当于,输入一个串S
,一个串T
,找到S
中所有T
的排列,返回它们的起始索引。
跟寻找字符串的排列一样,只是找到一个合法异位词(排列)之后将起始索引加入res
即可。
代码如下:
public static boolean checkInclusion(String s1, String s2) {
if(s1.length()>s2.length()){
return false;
}
char[] str1=s1.toCharArray();
char[] str2=s2.toCharArray();
//
int[] sArr=new int[26];//26是因为值包含小写字母
int[] tArr=new int[26];
//初始化
int valid=0;
for (int i = 0; i < s1.length(); i++) {
sArr[str1[i]-'a']++;
if(sArr[str1[i]-'a']==1){
valid++;//有效的
}
}
int left=0,right=0;
int count=0;
//遍历
while(right<s2.length()){
int ch=str2[right]-'a';
right++;
if(sArr[ch]!=0){//判断是否存在
tArr[ch]++;
if(tArr[ch]==sArr[ch]){
count++;
}
}
while(right-left>=s1.length()){//超出窗口范围
if(valid==count){
return true;
}
int temp=str2[left]-'a';
left++;
if(sArr[temp]!=0){
if(tArr[temp]==sArr[temp]){
count--;
}
tArr[temp]--;
}
}
}
return false;
}
LeetCode 438题、LeetCode 567 题、LeetCode 3 题等等。。
上一篇: 帮忙看下怎么会返回null