网站上传后怎么访问,网站建设官网制作平台,怎么在网络推广自己的产品,上海专业网站制作设计绪论#xff1a;冲击蓝桥杯一起加油#xff01;#xff01; 每日激励#xff1a;“不设限和自我肯定的心态#xff1a;I can do all things。 — Stephen Curry” 绪论#xff1a; 本章是算法训练的第二章----滑动窗口#xff0c;它的本质是双指针算法的衍生所以我将… 绪论冲击蓝桥杯一起加油 每日激励“不设限和自我肯定的心态I can do all things。 — Stephen Curry” 绪论 本章是算法训练的第二章----滑动窗口它的本质是双指针算法的衍生所以我将他们放到了连续的篇章若看完双指针算法再来看本章会相对来说轻松点传送阵,后续还将继续持续更新算法三天一更直到蓝桥杯结束敬请期待~ ———————— 早关注不迷路话不多说安全带系好发车啦建议电脑观看。 滑动窗口
本质其实是使用双指针暴力解法控制移动指针下标的方式得到一片区间类似像一个窗口并且这个双指针在移动过程中若从分析题目得知其单调性让指针始终从左往右的移动那么该双指针所指向的区间就是滑动窗口
记住 滑动窗口就是暴力双指针解法衍生出来的一般分析出left、right指针都是一直往右移的那么就表示为滑动窗口
在解题时若见连续子数组子串一般都可以尝试用滑动窗口算法
滑动窗口具体怎么用
最基本模板
1. left 0right 0
2. 进窗口维护窗口的信息
3. 判断根据窗口 信息判断 是否出窗口可能为循环一次出多个窗口1. 出窗口更新结果位置不固定
根据题目放到合适的位置这个多练几道题就能很轻松的掌握了如下图 正确性因为是利用单调性分析得出的他们同时像右移并且不用向左移动规避了很多没必要的枚举行为所以本质是分析出来的就题论题
时间复杂度双指针始终都是往右移的最大情况n n 2n O(N)
具体训练
1. 长度最小的子数组
题目 分析题目并提出解决方法
暴力解法将所有子数组遍历出来当遍历到一个区间后计算结果如下图 但这样遍历时间复杂度N2* 计算结果N就会导致时间复杂度非常大O(N3)记住像这种不断增加的线性区间可以提前将每个区间的值算出来然后存储在数组中前缀和但此处仅仅浅浅的用了下后面就会更新详细前缀和算法这样对计算结果的过程就能被优化为常数时间复杂度
具体优化方法如下 先遍历一遍为了计算区间的值 使用sum记录 left ~ right 区间的值right每走一步就加上一步的值 并且我们遍历的过程也不是无脑的遍历而是当结果一定不可是后面区间后那么就直接跳过不算了如下 而此时发现right不用再移动回来了因为在移动虽然满足条件但len长度一定会增大 从而可以让left移动一步继续遍历其他区间
因为这段区间的值可以快速的算出来只需要sum - left位置的值即可所以也得知他其实就是滑动窗口 最终我们就能通过滑动窗口的基本模板来遍历这个数组最终得到如下图滑动窗口移动过程 直到最后right移动到最后
为何滑动窗⼝可以解决问题并且时间复杂度更低
这个窗⼝寻找的是以当前窗⼝最左侧元素记为 left1 为基准符合条件的情况。也 就是在这道题中从 left1 开始满⾜区间和 sum target 时的最右侧记为right1 能到哪⾥。我们既然已经找到从 left1 开始的最优的区间那么就可以⼤胆舍去 left1 。但是如 果继续像⽅法⼀⼀样重新开始统计第⼆个元素 left2 往后的和势必会有⼤量重复 的计算因为我们在求第⼀段区间的时候已经算出很多元素的和了这些和是可以在计算 下次区间和的时候⽤上的。此时 rigth1 的作⽤就体现出来了我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始往后找满⾜ left2 元素的区间此时 right1 也有可能是满 ⾜的因为 left1 可能很⼩。 sum 剔除掉 left1 之后依旧满⾜⼤于等于target 。这样我们就能省掉⼤量重复的计算。这样我们不仅能解决问题⽽且效率也会⼤⼤提升。 时间复杂度虽然代码是两层循环但是我们的 left 指针和 right 指针都是不回退的两者 最多都往后移动 n 次。因此时间复杂度是 O(N)。
题解核心逻辑源码
诸多细节已注释到代码中见下
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {// 通过暴力解法分析题目可知我们可以使用滑动窗口也就是left right双指针都只需要往右移不用恢复回来向左移int sum 0,res INT_MAX;//循环for(int left 0,right 0;right nums.size();right){//进窗口://本质就是将right下标指向的值添加到sum计数器中sum nums[right];//并且right向后移动 //判断://一般来说都是判断是否需要出窗口本题也就是判断sum 是否大于 target若大于了就需要出窗口了//该判断也是一定要按题意来的本题对于大于等于target的值后就不再需要往后遍历了所以就出窗口//所以我们需要知道什么时候出窗口它的具体条件是什么while(sum target){//记录答案://记录答案一般来说就是最大或最小值//一般来说都是查看当前区间的值 是否满足最大或者最小若满足就保存否则跳过//本题是找最小的长度所以说我们需要判断该区间是否最小res min(res,right - left 1);//出窗口//就比较简单一般来说就是将left上的值从当前区间sum计数器中减去//本质也就是记录之前的值然后要更新成新的值了//减去left的值并让left移动形成新的区间sum - nums[left];left;}}return res INT_MAX ? 0 : res;}
};2. 无重复字符的最长子串
题目 分析题目并提出解决方法 通过上图就能很快的认知到题目的目的 找到一个最长不包含重复字符的字串
暴力解法很好想遍历呗遍历所有情况最终记录最短的即可但能不能优化呢
其中不难发现条件中的不能出现重复那么在我们遍历的过程中若出现了重复的是不是就可以把之前的记录了然后再舍弃最后得到新满足的区间在继续往后记录查找。
那如何快速的判断是否出现重复字符呢
hash表通过在遍历的过程中通过hash表记录遍历过的字符当hash中对应字符的值大于1后就表示出现了重复
题解核心逻辑 当区间出现重复字符的时候left就需要往移但只移动一步的话很明显right肯定还将碰到重复的值对于上图来说所以说我们需要将left移动到重复值的下一个位置 right不用回来继续往右移即可因为left就是将重复的给跳过了所以区间中一定不会出现重复的了 那么到此就发现它又是一个滑动窗口
那么就结合滑动窗口的基本模板就本题分析修改判断以及进窗口出窗口该怎么写 分析得出
class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() 0) return 0;int hash[128] {0};int res INT_MIN;for(int left 0,right 0;right s.size() ; right){//进窗口hash[s[right]];//针对s[right]字符进窗口//判断若出现重复字符while(hash[s[right]]1){//出窗口hash[s[left]]--;left;}//每次都记录这次不再内部记录是因为进去后是出现了重复了字符了记录的长度就不对了//他不想上一题有冗余度大于等于target都行res max(res,right - left 1);}return res;}
};3. 最大连续1的个数 III
题目 分析题目并提出解决方法
分析暴力解法
可以用双指针来确定连续的1的区间然后对于可翻转0通过记录个数zero当zero个数大于k后代表区间不满足条件了right就不能移动需要移动left。再重新遍历所有新区间最终得到所有情况。
具体如下图 当正常枚举时zero的个数为k后则right就不能再继续往后了该left移动了 优化 而left若只移动一步则left ~ right 区间内 的zero还是等于k如上图那么长度肯定不会增加right就没有必要重新回来枚举。 所以left一个不断移动直到让 left ~ right 区间内zero不等于k 再继续移动right此处就有可知left right都是一直往右移动所以可以使用滑动窗口
题解核心逻辑
最终得出滑动窗口模板分析如下图
class Solution {
public:int longestOnes(vectorint nums, int k) {int zero 0,res 0;for(int left 0,right 0; right nums.size();right){//进窗口if(nums[right] 0){zero;}//判断当0的个数大于了k表示子数组不符合条件了while(zero k){//出窗口if(nums[left] 0){zero--;}left;}res max(res,right - left 1);}return res;}
};4. 将 x 减到 0 的最小操作数
题目 分析题目并提出解决方法
题目要求找到从左右最少次数删除得到0 但若直接从正面想每次左右删除可能性非常多非常难写到底先左还是先右
此时我们可以反过来思考下
正难则反
既然想两边比较困难那么在线性中选择了两左右两边那么中间就是单独出来的 那么就转换成了找 最长、子数组 的长度所有元素的和正好等于targetsum - x
不难发现它和我们之前做的第一题相反1. 长度最小的子数组
题解核心逻辑
那么就可以尝试用双指针遍历所有区间查找 当left ~ right 区间大小大于等于target 此时right不用再移动了因为需要找的事刚好等于target在移动只会更大 所以需要移动left 但移动left后right不需要再回来重新遍历因为只会更小 所以right和left都是始终向右移动的也就是滑动窗口
class Solution {
public:int minOperations(vectorint nums, int x) {//分析得知使用滑动窗口找到值为 target (nums所有值 - x) d 最大连续子数组int target accumulate(nums.begin(),nums.end(),0) - x;int n nums.size();if(target 0) return -1;int sum 0,len -1;for(int left 0,right 0;right n;right){//进窗口sum nums[right];//sum存储值找值为target的最大连续子数组//判断while(sum target){//出窗口sum - nums[left];if(left n){left;}}//记录结果找到值为target就记录一下if(sum target){len max(len,right - left 1);}}if(len -1){return -1;}return n - len;}
};5. 水果成篮
题目 分析题目并提出解决方法 分析题目可知题目所需为在数组中找到最长的子数组并且水果类型不超过两种就很有滑动窗口的特性所以我们直接上滑动窗口
题解核心逻辑
使用双指针
当left右移后水果类型kinds的变化 不难发现right没有必要回来到left位置重新左移遍历而事等待水果个数变小left移动后再继续右移
所以left、right都是始终保持右移的也就是滑动窗口 算法原理
class Solution {
public:int totalFruit(vectorint fruits) {int kinds 0;//记录水果类型个数int hash[100010] { 0};//记录水果出现次数int res 0;//结果//最终要找的是最大的子数组长度for(int left 0,right 0;right fruits.size();right){//进窗口。水果的个数小于2时if(kinds 2){if(hash[fruits[right]] 0){kinds;//如果水果没有出现过 类型就要}hash[fruits[right]];}//当水果类型超过2种的时候就要出窗口了while(kinds 2){hash[fruits[left]]--;if(hash[fruits[left]] 0){kinds--;}left;}res max(res,right - left 1);}return res;}
};6. 找到字符串中所有字母异位词
题目 分析题目并提出解决方法
分析题目可知本题题意为
判断两个字符串是否是异位词字符相同可能顺序不同
直接通过两个hash表存储着他们各自字符的个数然后比较这些个数是否相同即可知道字符串是否相同若个数相同则代表元素相同只不过顺序不同
题解核心逻辑
这样我们就能得知方法 暴力解法
先获取目标字符串个数使用双指针指向该相同个数的字符串区间移动遍历比较一下和目标字符串中的元素个数是否都相同其中不难看出来left ~ right区间中right其实不需要回来因为长度是固定的所以该区间只需要不断往前也就是left、right不断最终就能遍历所有区间。 所以因为left、right不断所以也就是滑动窗口
class Solution {
public:bool Check(int hash1[26],int hash2[26]){for(int i 0;i 26;i){if(hash1[i] ! hash2[i]){return false;}}return true;}vectorint findAnagrams(string s, string p) {int hash1[26] {0};//存储滑动窗口中元素的个数int hash2[26] {0};//存储目标个数for(auto c : p){hash2[c-a];}vectorint res;for(int left 0,right 0;right s.size(); right){//进窗口hash1[s[right] - a];if(right - left 1 p.size()){hash1[s[left] - a]--; left;}if(Check(hash1,hash2)){res.push_back(left);}}return res;}
};其中对于Check检查字符串是否为异位词函数来说本质也还是遍历两个数组26次虽然微不足道但还能优化具体如下 其中使用count记录有效字符个数何为有效
在滑动窗口滑动的过程中窗口内的元素决定了有效字符个数有效字符 根据题意要找的是对应字符串中的相同字符那么在滑动窗口中进窗口若进窗口的字符和对应字符串中的某个字符相等字符相等且窗口内的已有个数小于等于对应窗口中的个数个数小于等于有效的count反之不有效count不变出窗口同样也需要判断出窗口的字符是否是有效字符若是则需要修改count–当count 对应字符串中的个数即代表刚好找到了那么就更新结果 总结就是使用一个count有效字符计数器来判断是否找到了
优化后代码
class Solution {
public:vectorint findAnagrams(string s, string p) {int hash1[26] {0};//存储滑动窗口中元素的个数int hash2[26] {0};//存储目标个数int count 0;for(auto c : p) hash2[c-a];vectorint res;for(int left 0,right 0;right s.size(); right){//进窗口hash1[s[right] - a];if(hash1[s[right] - a] hash2[s[right] - a]){count;}if(right - left 1 p.size()){if(hash1[s[left] - a] hash2[s[left] - a]){count--;}hash1[s[left] - a]--;left;}if(count p.size()){res.push_back(left);}}return res;}
};7. 串联所有单词的子串
题目 分析题目并提出解决方法
分析题目画出下图 理解题目所需从s中找到w字符串数组的不同排列情况 如下图w : “foo”、“bar” 那么s中符合条件的如下画横线处 通过图像我们不难看出假设把s和w中的字符串以其s内部的字符串长度为划分看出一个个字符 那么就将变成如下图形式 那么本题就很前面走的一题非常相似找异位词 所以使用同样的方法只不过此时left和right的移动需要改变从w中字符串长度 其中注意的是 要遍历所有情况也就是改变left的起始位置 [ 0 ~ len这样才能遍历所有情况具体如下不同颜色的横线
题解核心逻辑
核心逻辑和找异位词一致 不同的是
left和right的移动长度需要修改比较时通过hash存储字符比较相同在最外层增加一个循环顾忌所有情况
更多细节见源码
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {//分析可知本题和字母异位词很像类似将字符串看成字符vectorint res;unordered_mapstring,int hash2;//存储words中个数int n_hash2 0;for(auto s : words){n_hash2;hash2[s];}int len words[0].size();for(int i 0 ; i len; i){//注意 hash1 、 count 需要放到内部初始化防止下一次遍历使用到上次的数据unordered_mapstring,int hash1;//存储个数int count 0;//同样使用 有效字符记录for(int left i,right i;right s.size();right len){string sub1 s.substr(right,len);//进窗口hash1[sub1];// hash2.count(sub1) 避免 hash2[sub1] 内部数据不存在时的创建该数据的消耗if( hash2.count(sub1) hash1[sub1] hash2[sub1]){count;}//判断是否出窗口窗口中的个数是否大于所找的字符串个数// 画图可知((right - left) / len) 1 为当前滑动窗口元素个数// n_hash2 为所找的字符串的元素个数if(((right - left) / len) 1 n_hash2){string sub2 s.substr(left,len);//if(hash2.count(sub2) hash1[sub2] hash2[sub2]){count--;}hash1[sub2]--;//出窗口left len;}if(count n_hash2){res.push_back(left);}}}return res;}
};8.最小覆盖子串
题目 分析题目并提出解决方法
分析题目可知本题从s字符串中找到最短的包含t字符串中所有字符的子串 如下图ADOBEC就包含了所有tABC、BECODEBA同样也包含所有、BANC 其中不难看出BANC最短所以他就是最终答案 具体如下图 那么就能推出暴力解法使用双指针遍历所有区间并且使用哈希表来判断是否已经包含t字符串了 但我们再暴力解法的情况下再分析看看是否符合滑动窗口
不难发现下面情况 right没必要回去了因为只有两种可能
left 右移区间改变但仍然符合条件那么right移动回来再往右找最终还会移动到相同的为止停下来因为条件没变right指向的地方仍然是最后一个值若left右移区间改变但不符合条件了那么right肯定会移动到原来位置再往右的位置才可能停下
题解核心逻辑
那么就是滑动窗口了 分析题意的下面滑动窗口模板 优化 同样是使用一个count进行记录有效字符个数代替使用hash表的比较记录但本题中他的条件不要一样并不需要找到异位词而是找到包含t中所有字符的即可而其中相同的字符可能会出现多次所以count只有在 滑动窗口中某个元素的个数 目标字符串的某个元素的个数时才和–因为假如 count 是 目标个数肯定不是小于小于不符合个数大于等于条件时都 的话那么可能会多算
记住count是有效字符个数我们要结合好题目所给的条件进行设置此题见题目中的注意事项可知“不少于”
class Solution {
public:string minWindow(string s, string t) {unordered_mapchar,int hash1;//存储滑动窗口内部数据unordered_mapchar,int hash2;//存储t字符中的元素for(auto c : t) hash2[c];int count 0;//维护一个有效字符个数计数器i、nt len INT_MAX;//用于比较长度找到最小的长度int l_res -1;for(int left 0,right 0; right s.size() ;right){//进窗口hash1[s[right]];//hash2.count(s[right])这里是防止hash2[s[right]]创建新的字符if(hash2.count(s[right]) hash1[s[right]] hash2[s[right]]) count;//判断while(count hash2.size()){//记录if(right - left 1 len){len right - left 1;l_res left;}//出窗口if(hash2.count(s[left]) hash1[s[left]] hash2[s[left]]) count--;hash1[s[left]]--;left;}}if(l_res -1) return ;return s.substr(l_res,len);}
};不使用容器
class Solution {
public:string minWindow(string s, string t) {int hash1[128] {0};//存储滑动窗口内部数据int hash2[128] {0};//存储t字符中的元素int kinds 0;for(auto c : t) {if(hash2[c] 0) kinds;//若果为0代表新类型hash2[c];}int count 0;//维护一个有效字符个数计数器int len INT_MAX,begin -1;//len记录最小的长度、begin记录最小长度的起始位置for(int left 0,right 0; right s.size() ;right){//进窗口hash1[s[right]];if(hash1[s[right]] hash2[s[right]]) count;//判断while(count kinds){//记录找到新的小的长度if(right - left 1 len){len right - left 1;begin left;}//出窗口if(hash1[s[left]] hash2[s[left]]) count--;hash1[s[left]]--;left;}}if(begin -1) return ;return s.substr(begin,len);}
};
