前言
滑动窗口是双指针的一种特例,可以称为左右指针,在任意时刻,只有一个指针运动,而另一个保持静止。滑动窗口路一般用于解决特定的序列中符合条件的连续的子序列的问题。
滑动窗口的时间复杂度是线性的,一般为
O
(
n
)
O(n)
O(n),滑动窗口的左右边界都不会向左滑动,向左滑动等于走回头路,是一种回溯的算法,很可能会陷入死循环。
滑动窗口是一种全遍历问题,一定会遍历到末尾的。
其本质思路在于:
- 初始化将滑动窗口压满,取得第一个滑动窗口的目标值
- 继续滑动窗口,每往前滑动一次,需要删除一个和添加一个元素,求最优的目标值
滑动窗口所解决的问题类型
一般来说,我们面对的最多的两个序列就是数组与字符串。
那么,滑动窗口解决的就是子序列与子数组的问题。
- 字符串类的滑动窗口问题
这类问题一般可以分为两类,单个字符串;两个字符串。两个字符串当中又可以按照连续序列与非连续序列进行划分。
对于两个字符串而言,一般是一个字符串作为母体,另一个字符串作为比较。
举几个力扣中题目的例子:
🅰️字符串的最小覆盖字串(非连续序列)
🅰️字符串的排列(连续序列)
🅰️字符串的所有字母异位词(连续序列)
🅰️无重复字符的最长子串(单个字符串)
🅰️最多包含连个重复字符的最长字串
🅰️最多包含k个重复字符的最长字串
以字符串的最小覆盖字串题目为例
对于字符串而言,两个字符串问题的滑动窗口的具体代码如下
Map<Character,Integer> window=new HashMap<>();
Map<Character,Integer> need=new HashMap<>();
int left=0;
int right=0;
int len=Integer.MAX_VALUE;
char [] array=s.toCharArray();
for(int i=0;i<p.length();i++)
{
need.put(p.charAt(i),need.getOrDefault(p.charAt(i),0)+1);
}
while(right<s.length())
{
char c=array[right];
right++;
if(need.containsKey(c))
{
windows.put(c,window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c)))
{
valid++;
}
}
while(valid==need.size())
{
char d=array[left];
if(right-left<len)
{
start=left;
len=right-left;
}
left++;
if(need.containsKey(d))
{
if(window.get(d).equals(need.get(d)))
{
valid--;
}
window.put(d,window.getOrDefault(d,0)-1);
}
}
}
return s.substring(start,start+len);
再来看一道题,并且思考滑动窗口的优化问题
无重复字符的最长字串
这道题可以直接套用我们的模板
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> window=new HashMap<>();
char []array=s.toCharArray();
int left=0;
int right=0;
int valid=0;
int len=0;
int start=0;
int sons=0;
while(right<s.length())
{
char c=array[right];
window.put(c,window.getOrDefault(c,0)+1);
right++;
while(window.get(c)>1)
{
char d=array[left];
window.put(d,window.getOrDefault(d,0)-1);
left++;
}
if(len<right-left)
{
len=right-left;
start=left;
}
}
return len;
}
}
但是这里分析一种情况,当s="abddd"的情况时,模板中是利用不断删减’a’,‘b’,‘d’,其实直接定位到第一个‘d’字符是最好的,来看这一种解法
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
int left = 0;
for(int i = 0; i < s.length(); i ++){
if(map.containsKey(s.charAt(i))){
left = Math.max(left,map.get(s.charAt(i)) + 1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-left+1);
}
return max;
}
}
- 数组类的滑动窗口问题
🅰️ 长度最小的子数组
🅰️ 滑动窗口的最大值
🅰️和为s的连续正数序列
🅰️子数组最大平均数
上面的每一种题目,相对于字符串的问题来说更加简单,有时候甚至不需要进行哈希集合的定义,而只需要进行简单的这个左右指针的移动,维护好窗口就行。
滑动窗口的技巧
使用滑动窗口的难点在于:什么时候应该移动右侧指针来扩大窗口,什么时候移动左侧指针来减小窗口。
我们来分析一下上面说的滑动窗口的最大值
这道题有一个额外的附加条件:滑动窗口的大小为k,这就可以称为我们缩小窗口的依据,从而方便的利用滑动窗口来解题。
我们在看一道题,最大子数组和
这道题几乎与前面的滑动窗口最大值类似,只不过题目中没有显式的提出缩小窗口的条件,需要我们自己去寻找。
class Solution
{
public int maxSubArray(int[] nums) {
int left=0;
int right=0;
int sum=0;
int maxsum=nums[0];
while(right<nums.length())
{
sum+=nums[right];
if(sum<0)
{
sum-=nums[left];
left++;
}
maxsum=Math.max(maxsum,sum);
}
int maxVal = nums[0];
for (int i = 1; i <nums.size(); i++) {
maxVal = max(maxVal, nums[i]);
}
return maxVal < 0 ? maxVal : maxsum;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)