滑动窗口详解

1年前 (2023) 程序员胖胖胖虎阿

131 0 0

前言

滑动窗口是双指针的一种特例，可以称为左右指针，在任意时刻，只有一个指针运动，而另一个保持静止。滑动窗口路一般用于解决特定的序列中符合条件的连续的子序列的问题。

滑动窗口的时间复杂度是线性的，一般为

(

)

O(n)

$O (n)$ ,滑动窗口的左右边界都不会向左滑动，向左滑动等于走回头路，是一种回溯的算法，很可能会陷入死循环。
滑动窗口是一种全遍历问题，一定会遍历到末尾的。
其本质思路在于：

初始化将滑动窗口压满，取得第一个滑动窗口的目标值
继续滑动窗口，每往前滑动一次，需要删除一个和添加一个元素，求最优的目标值

滑动窗口所解决的问题类型

一般来说，我们面对的最多的两个序列就是数组与字符串。
那么，滑动窗口解决的就是子序列与子数组的问题。

字符串类的滑动窗口问题
这类问题一般可以分为两类，单个字符串；两个字符串。两个字符串当中又可以按照连续序列与非连续序列进行划分。
对于两个字符串而言，一般是一个字符串作为母体，另一个字符串作为比较。
举几个力扣中题目的例子：
🅰️字符串的最小覆盖字串（非连续序列）
🅰️字符串的排列（连续序列）
🅰️字符串的所有字母异位词（连续序列）
🅰️无重复字符的最长子串（单个字符串）
🅰️最多包含连个重复字符的最长字串
🅰️最多包含k个重复字符的最长字串
以字符串的最小覆盖字串题目为例

对于字符串而言，两个字符串问题的滑动窗口的具体代码如下

//母字符串s,匹配字符串p
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();
//将匹配字符串p放入Map中去
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))
	{
		//window遍历了所有的从left到right的值
		//很可能这些值中的某个字符多了，因为需要包含p的所有字符
		windows.put(c,window.getOrDefault(c,0)+1);
		//这时候就要思考多种情况的出现
		//不能need中一包含这个字符，我就进行valid++
		//可能在字符串p中这个字符是重复的，有多个，所以
		//需要记录字符的个数，这也是为什么用Map的原因
		if(window.get(c).equals(need.get(c)))
		{
			valid++;
		}
	}
	//什么时候进行窗口的更新
	//满足基本条件
	//什么叫满足基本条件
	//比如说最短覆盖字串，我们就要满足覆盖这个基本条件
	//但是这个时候的覆盖可能不是最短的
	//所以我们通过缩小左边框来进行最小的判断。

	//注意下面是通过need的长度而不是p的长度来判断。
	//p中可能有很多重复的字符
	//你要注意上面valid进行一次更新是不容易的，
	//所有重复的都进入windowz这个窗口，我才能加一次
	while(valid==need.size())
	{
		char d=array[left];
		//你要想清楚，什么时候进行你想要的数据的提领
		//因为left，可能下一次你最基本的条件都不能保证
		//所以这时候，我就要进行记录
		//这时候进行思考，怎么样最小
		//我们一般常见的作法是什么，循环比较，设置一个最大值
		//然后不断比较
		if(right-left<len)
		{
			start=left;
			//注意right++与left++什么时候做对于你下面的
			//len需不需要减1加1至关重要
			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) {
        //需要window这个hashmap来比较数据
        //这道题考虑的是字串的问题，比较麻烦，字串必须是连续的
        //如果考虑的是子序列的问题，这题就比较简单，直接使用可以去重的一类数据结构拿住所有的不重复字符就行
        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)
            {
                //这时候不能直接更新结果，你已经大于1了
                char d=array[left];
                window.put(d,window.getOrDefault(d,0)-1);
                left++;
            }
            //我觉得在这里记录结果不太好，每一次都要更新，其实是没有必要的
            //已阅，狗屁不通，不放在这里，难道放在内循环里，没有重复的都不要？
            // len=len>right-left?len:right-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;
	}
}