滑动窗口算法篇：连续子区间与子串问题

1.滑动窗口原理

那么一谈到子区间的问题，我们可能会想到我们可以用我们的前缀和来应用子区间问题，但是这里对于子区间乃至子串问题，我们也可以尝试往滑动窗口的思路方向去进行一个尝试，那么说那么半天，滑动窗口是什么呢？它怎么用呢？

滑动窗口这名字看起来很高大尚，但是实际上所谓的滑动窗口，就是维护两个指针left和right，那么这两个指针中间的内容就是我们的窗口，那么至于所谓的“滑动”,那么我们可以通过移动我们的左右两个指针来达到让这个窗口的沿着数组移动。

那么介绍完我们滑动窗口是什么，我再来说一下滑动窗口怎么用，对于滑动窗口问题，其实这类问题的解决的思想我觉得和我们的二分答案法的一个思想其实是有一点相近的，首先我们滑动窗口的题通常有一个特征，那么就是找一个子数组或者子串，但是我们找的这个子数组或者子串不是一般的子数组或者子串，它通常是要满足一个性质，并且我们要寻找的该子串是满足性质的一个边界点。

那么我们会定义一个滑动窗口也就是左指针与右指针，这个窗口内要维护的内容通常要满足这个性质，并且该性质与我们的窗口的长度存在一种单调性，窗口长度增大，那么意味着越容易达到满足该性质，反之长度越小，则不容易达到满足该性质，那么滑动窗口的长度扩大就是通过让右指针向右移动从而扩大右边界，那么当我们的滑动窗口内的内容达到该性质的时候，那么这就和我上文说的我们要寻找的子串有关，我们的目标子串不仅是满足该性质，而且是满足该性质的一个边界，所以这里我们滑动窗口内达标的一个子串它虽然满足该性质，但是它不一定是满足该性质的一个边界，由于我们窗口长度减小，那么越不容易达到该性质，那么我们此时就缩小左边界，也就是左指针往左移动，那么此时我们窗口长度在减小，那么我们就会缩小到该内容达到性质边界点的位置
在这里插入图片描述

那么我们滑动窗口的性质与窗口的长度的单调性不一定是长度越长越容易达到该性质，也可能是长度越长越不容易达到该性质，那么这得看具体题目，那么我们滑动窗口的原理总结来说就是：

首先识别这是一个子数组或者子串问题，并且要求的子数组与子串是满足特定性质的边界，那么我们就定义左右两个指针接着确定我们这个窗口里面的内容要维护要达到的性质，然后确定该性质与窗口长度的单调性。

那么相信你看完滑动窗口的原理你肯定还是一知半解的感觉，但没关系，接下来下文我会通过几道题来具体给你阐述我是如何通过滑动窗口的一个算法思想以及原理来解决这类题目的，以及该算法的大致处理流程是什么，那么不要走开，希望你耐心看完，相信我，你一定会理解并掌握该算法的思想。

2.应用

题目一：累加和>=k的长度最小的子数组难度：EZ

题目：现在我们有一个数组，那么数组内的元素全部都为正数，那么我们要求累加和大于等于k的长度最小的子数组。

题目思路：那么这里看到子数组与子串首先就得敏感起来，那么这题的解法有很多，对于我想到的就有三个，如果还有其他算法能够解决该题的，欢迎在评论区补充，那么我们这题肯定可以通过滑动窗口来解决，还可以通过前缀和来解决，也还可以用二分答案法来解决。

那么这题我就讲一下我们的滑动窗口怎么做这道题，以及我是如何运用上面的算法思想的，那么这里我们分析一下题目，首先根据题目我们的子数组是满足某种性质，该性质就是累加和大于等于k，但是为什么该子数组就是特殊的子数组呢，因为我们要寻找的目标子数组是累加和大于等于k的长度最小的子数组，特殊就特殊在它要长度最小最小，也就意味着我们有很多满足该性质也就是累加和大于等于k的子数组，但是它的长度在其中不一定是最小，而这里所谓的最小，就是我们所说的满足该性质的一个边界，那么满足该性质的边界的子数组就是我们要得到的目标子数组。

那么接下来我们就定义一个滑动窗口，第二步就是确定我们该窗口里面的内容要满足的性质，那么对于这题来说，我们该窗口里的内容要满足的性质就是累加和大于等于k，那么我们再来分析该性质与窗口长度的单调性关系，那么我们知道由于数组内的元素都是正数，那么意味着我们窗口长度越大，那么我们窗口的累加和越大，那么就越容易达到满足我们窗口要维护的性质也就是大于等于k。

那么最开始我们的窗口的初始话是在数组的左边界，窗口长度为1，左右指针都指向下标为0的元素，也就是窗口内现在只有下标为0的元素(注意这里我们定义的窗口的左右边界是是左闭右闭的区间[L,R],如果你定义的是左闭右开[L,R)的区间的窗口的话，那么初始化窗口的右指针就该指向下标为1的位置)，那么我们窗口如果不满足该性质的话，那么我们就往右扩，那么直到我们窗口内的内容达标，那么此时窗口内的内容是累加和大于等于k的子数组，但是该子数组不一定就是最小的子数组，也就是它不一定就落在性质的边界位置处，所以此时我们缩小我们的窗口，左指针向左移动，那么直到我们达到如果左指针在往左移动一步，那么该窗口的内容就不满足该性质也就是累加和大于等于k，那么这就找到了满足该性质的边界以右边界位置处结尾的子串，那么我们记录答案，我们就重复上面的步骤，一旦我们窗口达标，那么我们就尝试缩小，那么最后记录的答案就是最终结果。

代码实现：

class solution
{
	public:
	int minlengtharray(vector<int>& arr,int k)
	{
		int l=0,r=0;
		int sum=0;
		int ans=INT_MAX;
		while(r<arr.size())
		{
			sum+=arr[r];
			if(sum<k)
			{
				r++;
			}else
			{
                //当窗口内的和大于等于k时，尝试缩小窗口
				while(sum>=k&&l<=r)
				{
					sum-=arr[l];
					l++;
				}
				ans=min(ans,r-l+1);
			}
		}
		return ans;
	}
}

那么这里我们说完解题思路，我们再来看看我们的滑动窗口是如何应用的，我们首先确定了我们的目标子数组满足的性质也就是累加和大于等于k并且它是满足该性质的边界因为要求最小长度的、，然后定义窗口，确定窗口要满足的性质以及与窗口长度的单调性关系，那么对于本体来说，窗口长度越大越容易满足该性质，接着就是不断的扩大以及缩小窗口，那么我们在此过程中，我们的左右指针是不会回退的，那么对于该题滑动窗口算法的时间复杂度就是遍历该数组的时间复杂度也就是o(N),那么滑动窗口也是解决该题的最优算法。

知道了这题怎么做以及滑动窗口的原理，那么这里我有一个思考题，读者可以先自行思考一下，我会在下文给出答案与解释。

那么假设我们这个数组里面的元素不全为正数而是有负数存在，那么请问该题还能用滑动窗口做吗？

答案是不行的，因为我们如果数组中有负数的话，那么此时我们窗口要维护要达到的性质也就是累加和大于等于k与我们的窗口长度的单调性就丧失了，那么我们窗口长度越大，我们知道如果数组的元素全是正式，那么窗口长度增大，窗口的累加和只可能增大，但是一旦有了负数的存在，我们窗口的长度增大，那么我们该窗口内的内容的累加和可能会增大可能会减小，所以不能应用，那么有负数的情况就只能用我们的前缀和来做了。

那么总结下来，滑动窗口算法的流程：

1.确定答案满足的性质

2.定义窗口，确定窗口要维护的性质，以及该性质与窗口长度的单调性关系

3.不满足窗口性质往右扩大，达到性质那么就从左边界缩小，记录答案

题目二：无重复字符的最长子串难度：MID

题目：现在有一个字符串，我们要找到该字符串的无重复字符的最小子串，返回这个子串，题目保证一定有有重复子串

题目分析：那么这里这道题看到子串先考虑一下滑动窗口，那么这里这里我们的子串满足的性质是无重复字符，并且要找的该子串是性质的边界，那么我们还是定义一个窗口，然后确定该窗口要维护的性质是里面的内容是无重复字符，那么我们分析单调性，那么我们扩大窗口，窗口长度增大，那么字符数量增大，那么越不容易满足该性质，反之窗口长度越小则容易满足性质，那么这题和我们之前普遍的单调性是反着来的。

那么我们还是一样，往有扩大窗口，每次扩大的时候，那么我们都尝试能否缩小窗口，那么我们这里则比较当前右边界i位置的字符，那么找i位置的字符右侧之前出现过的最晚位置在不在窗口里面，如果在的话，说明有重复，那么我们就只能缩小左边界到该该位置的下一位，如果不在，那么则继续往右扩大。每一次扩充都得检查，让我们窗口里面维护的是无重复字符的子串

代码实现：

class solution
{
	public:
	void maxlengthstring(string& a,string& ans)
	{
		int l=0,r=0;
		unordered_map<char,int> value;
		int start=0;
		int len=-1;
		while(r<a.size())
		{
			if(value.find(a[r])!=a.end())
			{
				if(a[r]>=l)
				{
					l=a[r]+1;
				}
				if(len<r-l+1)
				{
					len=r-l+1;
					start=l;
				}
			}
			value[a[r]]=r;
			r++;
		}
		ans=a.substr(start,len);
		return ans;
	}
}

题目三：寻找满足特定数量的字符的最小长度子串难度：MID

题目：现在有一个字符串，我们要找到满足特定数量字符的最小子串。

注：我们这里的子串只要求满足特定数量的字符，其中可以包含其他字符，比如现在要找含有2个a，3个b的最小子串，那么对于该子串aabbbee是符合性质的

题目思路：那么这里我们子串的性质是要满足特定数量的字符，那么这里我们可以定义一个窗口，维护的性质就是满足特定数量的字符，那么我们窗口长度越大，那么越容易满足该性质，反之窗口长度越小则越不容易满足该性质，那么这里我们可以准备一张哈希表记录特定字符需要的数量，以及我们定义一个变量debt来表示需要的总数量，那么我们往右扩充窗口的时候，我们检查该窗口的右边界位置是否是特定字符，那么是的话，就在哈希表中的记录减一，然后总数量减一。

那么沃恩这道题得注意我们缩小我们窗口的时机，我们这里只有当我们的总数量达标之后才可以，那么如果说我们某一个字符在这个窗口内的数量以及达标或者超过需要的数量，比如要2个a，但是窗口内的该字符数量有3个a了，但是如果说我们其他字符还有缺的话，那么我们仍然要往右扩充，指导每个字符都达到大于等于规定数量，也就是debt小于或者等于0时我们就缩小窗口。

那么对于缩小左边界如果该左边界是其他字符，那么我们直接缩小，但是如果是特定字符，那么我们得查询哈希表，看看该字符的数量，如果是负数的话，那么说明超过规定的数量，因为我们右边界有该字符我们都是直接在哈希表对应位置处减减，缩小玩之后，我们再在表中对负数位置记录加一，如果是0，那么在缩小则会小于规定数量，那么只能停止缩小在往右扩，并且每次缩小的是特定字符的话，我们还要将debt变量加一如果debt是负数的话，那么当不能缩小该特定字符并且debt变量为0时记录答案。

代码实现：

class Solution {
public:
    string minWindow(const std::string& s, const std::unordered_map<char, int>& required) {
        int debt = 0;
        for (const auto& pair : required) {
            debt += pair.second;
        }
        
        int l = 0, r = 0;
        int minLength = INT_MAX;
        string result = "";
        unordered_map<char, int> count = required;

        while (r < s.size()) {
            if (count.find(s[r]) != count.end()) {
                    debt--;
                count[s[r]]--;
            }

            while (debt <=0) {
                if (r - l + 1 < minLength) {
                    minLength = r - l + 1;
                    result = s.substr(l, minLength);
                }

                if (count.find(s[l]) != count.end()) {
                     if(count[s[l]]==0)
                     {
                         break
                     }
                    count[s[l]]++;
                    if(debt+1>0)
                    {
                        break;
                    }
                        debt++;
                    
                    }
                }
                l++;
            }
            r++;
        }
        return result;
    }
};