文章目录

【算法笔记】滑动窗口算法原理深度剖析前言一.长度最小的子数组1.1题目1.2思路分析1.3算法流程1.4正确性证明1.5代码实现

二.无重复字符的最长字串2.1题目2.2思路分析2.3代码实现

四.找到字符串中所有字母异位词4.1题目4.2思路分析4.3代码实现

算法总结后言

哈喽各位小伙伴大家好上期我们讲了双指针算法原理今天我们继续讲解滑动窗口算法原理。

话不多说咱们进入正题向大厂冲锋

1.1题目

这里当right越界时说明我们枚举了所有情况直接返回结果即可。

class

left0,right0;rightnums.size();right){sumnums[right];//进窗口while(sumtarget){Minmin(Min,right-left1);//更新结果sum-nums[left];//出窗口}}return

MinINT_MAX?0:Min;}

lengthOfLongestSubstring(string

{int

left,right,ns.size();·leftright0;while(rightn){hash[s[right]];//进窗口while(hash[s[right]]1){hash[s[left]]--;//出窗口}retmax(ret,right-left1);//更新结果right;}return

retINT_MIN?0:ret;}

left0,right0,k0,nfruits.size();rightn;right){if(hash[fruits[right]]0)//进窗口{k;//种类增加}hash[fruits[right]];//记录个数while(k2){hash[fruits[left]]--;if(hash[fruits[left]]0)//种类减少{k--;}left;//出窗口}ansmax(ans,right-left1);//更新结果}return

ans;}

left0,right0,ns.size();rightn;right){char

ins[right];//进窗口if(hash2[in-a]hash1[in-a]){count;//有效字符增加}if(right-left1p.size()){char

outs[left];//出窗口if(hash2[out-a]--hash1[out-a]){count--;//有效字符减少}}if(countp.size()){ret.push_back(left);//保存结果}}return

ret;}

a:words){hash1[a];//填充哈希表存储单词个数}int

lenwords[0].size(),nwords.size();for(int

string

lefti,righti,count0;rightlens.size();rightlen){string

ins.substr(right,len);hash2[in];//填充哈希if(hash1.count(in)hash2[in]hash1[in])//判断是否有效字符串{count;//更新有效单词个数}if(right-left1len*n)//出窗口{string

outs.substr(left,len);if(hash1.count(out)hash2[out]hash1[out])//判断是否有效字符串{count--;//更新有效单词个数}hash2[out]--;//更新哈希leftlen;}if(countn){ret.push_back(left);//更新结果}}}return

ret;}

滑动窗口就是根据题目信息在暴力枚举的条件下利用单调性优化用同向双指针快速筛选掉一些不必要的遍历情况。

在O(N)的复杂度下完成所有情况的枚举从而解题的算法。

这就是滑动窗口算法原理的深度剖析。

总而言之滑动窗口就是在暴力枚举的情况下利用单调性使用同向双指针在O(N)的复杂度完成枚举的算法。

算法流程并不重要重要的是背后的算法原理推到和证明。

大家自己下去好好消化。

今天就分享到感谢各位的耐心垂阅咱们下一期见拜拜~