比较好的网站搭建论坛,为了爱我可以做任何事俄剧网站,杭州如何做百度的网站推广,大学网站建设的目标1.滑动窗口原理
那么一谈到子区间的问题#xff0c;我们可能会想到我们可以用我们的前缀和来应用子区间问题#xff0c;但是这里对于子区间乃至子串问题#xff0c;我们也可以尝试往滑动窗口的思路方向去进行一个尝试#xff0c;那么说那么半天#xff0c;滑动窗口是什么…
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(vectorint arr,int k){int l0,r0;int sum0;int ansINT_MAX;while(rarr.size()){sumarr[r];if(sumk){r;}else{//当窗口内的和大于等于k时尝试缩小窗口while(sumklr){sum-arr[l];l;}ansmin(ans,r-l1);}}return ans;}
}那么这里我们说完解题思路我们再来看看我们的滑动窗口是如何应用的我们首先确定了我们的目标子数组满足的性质也就是累加和大于等于k并且它是满足该性质的边界因为要求最小长度的、然后定义窗口确定窗口要满足的性质以及与窗口长度的单调性关系那么对于本体来说窗口长度越大越容易满足该性质接着就是不断的扩大以及缩小窗口那么我们在此过程中我们的左右指针是不会回退的那么对于该题滑动窗口算法的时间复杂度就是遍历该数组的时间复杂度也就是o(N),那么滑动窗口也是解决该题的最优算法。
知道了这题怎么做以及滑动窗口的原理那么这里我有一个思考题读者可以先自行思考一下我会在下文给出答案与解释。
那么假设我们这个数组里面的元素不全为正数而是有负数存在那么请问该题还能用滑动窗口做吗
答案是不行的因为我们如果数组中有负数的话那么此时我们窗口要维护要达到的性质也就是累加和大于等于k与我们的窗口长度的单调性就丧失了那么我们窗口长度越大我们知道如果数组的元素全是正式那么窗口长度增大窗口的累加和只可能增大但是一旦有了负数的存在我们窗口的长度增大那么我们该窗口内的内容的累加和可能会增大可能会减小所以不能应用那么有负数的情况就只能用我们的前缀和来做了。
那么总结下来滑动窗口算法的流程 1.确定答案满足的性质 2.定义窗口确定窗口要维护的性质以及该性质与窗口长度的单调性关系 3.不满足窗口性质往右扩大达到性质那么就从左边界缩小记录答案 题目二无重复字符的最长子串 难度MID
题目现在有一个字符串我们要找到该字符串的无重复字符的最小子串返回这个子串题目保证一定有有重复子串
题目分析那么这里这道题看到子串先考虑一下滑动窗口那么这里这里我们的子串满足的性质是无重复字符并且要找的该子串是性质的边界那么我们还是定义一个窗口然后确定该窗口要维护的性质是里面的内容是无重复字符那么我们分析单调性那么我们扩大窗口窗口长度增大那么字符数量增大那么越不容易满足该性质反之窗口长度越小则容易满足性质那么这题和我们之前普遍的单调性是反着来的。
那么我们还是一样往有扩大窗口每次扩大的时候那么我们都尝试能否缩小窗口那么我们这里则比较当前右边界i位置的字符那么找i位置的字符右侧之前出现过的最晚位置在不在窗口里面如果在的话说明有重复那么我们就只能缩小左边界到该该位置的下一位如果不在那么则继续往右扩大。每一次扩充都得检查让我们窗口里面维护的是无重复字符的子串
代码实现
class solution
{public:void maxlengthstring(string a,string ans){int l0,r0;unordered_mapchar,int value;int start0;int len-1;while(ra.size()){if(value.find(a[r])!a.end()){if(a[r]l){la[r]1;}if(lenr-l1){lenr-l1;startl;}}value[a[r]]r;r;}ansa.substr(start,len);return ans;}
}题目三寻找满足特定数量的字符的最小长度子串 难度MID
题目现在有一个字符串我们要找到满足特定数量字符的最小子串。
注我们这里的子串只要求满足特定数量的字符其中可以包含其他字符比如现在要找含有2个a3个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_mapchar, 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_mapchar, 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(debt10){break;}debt;}}l;}r;}return result;}
};3.结语
那么这就是本篇文章关于滑动窗口的一个全部内容那么滑动窗口的思想其实我们发现和二分有点相似是寻找满足性质边界的一个答案那么由于这里的单调性是和我们的窗口的长度有关所以我们能够通过窗口的长度的扩大与缩小来线性的逼近我们的边界点而不用像二分那样每次取中点那样逼近
那么如果本篇文章让你有所收获那么我们便感到非常开心那么我会持续更新希望你能够多多关注与支持如果该文章由帮组到你那么也留下个一键三连来支持一下你的支持就是我创作的最大动力
