wordpress 全局js,北京网站搜索引擎优化,网站建设医药,创业平台官网【算法笔记】滑动窗口算法原理深度剖析 #x1f525;个人主页#xff1a;大白的编程日记
#x1f525;专栏#xff1a;算法笔记 文章目录 【算法笔记】滑动窗口算法原理深度剖析前言一.长度最小的子数组1.1题目1.2思路分析1.3算法流程1.4正确性证明1.5代码实现 二.无重复…【算法笔记】滑动窗口算法原理深度剖析 个人主页大白的编程日记
专栏算法笔记 文章目录 【算法笔记】滑动窗口算法原理深度剖析前言一.长度最小的子数组1.1题目1.2思路分析1.3算法流程1.4正确性证明1.5代码实现 二.无重复字符的最长字串2.1题目2.2思路分析2.3代码实现 三.水果成蓝3.1题目3.2思路分析3.3代码实现 四.找到字符串中所有字母异位词4.1题目4.2思路分析4.3代码实现 五.串联所有单词的子串5.1题目5.2思路分析5.3代码实现 算法总结后言 前言 哈喽各位小伙伴大家好上期我们讲了双指针算法原理今天我们继续讲解滑动窗口算法原理。话不多说咱们进入正题向大厂冲锋 一.长度最小的子数组
1.1题目
题目长度最小的子数组
1.2思路分析
这里我们根据暴力算法借助单调性优化利用滑动窗口解决问题。
1.3算法流程 1.4正确性证明 1.5代码实现
这里当right越界时说明我们枚举了所有情况直接返回结果即可。
class Solution {
public:int minSubArrayLen(int target, vectorint nums){int MinINT_MAX;int sum0;for(int left0,right0;rightnums.size();right){sumnums[right];//进窗口while(sumtarget){Minmin(Min,right-left1);//更新结果sum-nums[left];//出窗口}}return MinINT_MAX?0:Min;}
};二.无重复字符的最长字串
2.1题目
题目无重复字符的最长字串
2.2思路分析 2.3代码实现
这里我们用字符数组存储字符信息方便我们判断我们。
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]{0};//存储字符信息int retINT_MIN;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;}
};三.水果成蓝
3.1题目
题目水果成蓝
3.2思路分析 3.3代码实现
class Solution {
public:int totalFruit(vectorint fruits) {int hash[100001]{0};//存储水果种类个数int ansINT_MIN;for(int 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;}
};四.找到字符串中所有字母异位词
4.1题目
题目找到字符串中所有字母异位词
4.2思路分析 4.3代码实现
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ret;int hash1[26]{0};int hash2[26]{0};for(auto a:p){hash1[a-a];}int count0;//记录有效字符个数for(int 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;}
};五.串联所有单词的子串
5.1题目
题目串联所有单词的子串
5.2思路分析 5.3代码实现
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {unordered_map string ,int hash1;//字符串哈希表vectorint ret;for(auto a:words){hash1[a];//填充哈希表存储单词个数}int lenwords[0].size(),nwords.size();for(int i0;ilen;i){unordered_map string ,int hash2;for(int 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)的复杂度完成枚举的算法。算法流程并不重要重要的是背后的算法原理推到和证明。大家自己下去好好消化。今天就分享到感谢各位的耐心垂阅咱们下一期见拜拜~
