【算法笔记】滑动窗口算法原理深度剖析

【算法笔记】滑动窗口算法原理深度剖析

🔥个人主页：大白的编程日记

🔥专栏：算法笔记

---

前言

哈喽，各位小伙伴大家好！上期我们讲了双指针算法原理，今天我们继续讲解滑动窗口算法原理。话不多说，咱们进入正题！向大厂冲锋！

一.长度最小的子数组

1.1题目

• 题目：长度最小的子数组
  

1.2思路分析

这里我们根据暴力算法借助单调性优化，利用滑动窗口解决问题。

1.3算法流程

1.4正确性证明

1.5代码实现

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

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int Min=INT_MAX;int sum=0;for(int left=0,right=0;right<nums.size();right++){sum+=nums[right];//进窗口while(sum>=target){Min=min(Min,right-left+1);//更新结果sum-=nums[left++];//出窗口}}return Min==INT_MAX?0:Min;}
};

二.无重复字符的最长字串

2.1题目

• 题目：无重复字符的最长字串
  

2.2思路分析

2.3代码实现

这里我们用字符数组存储字符信息方便我们判断我们。

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};//存储字符信息int ret=INT_MIN;int left,right,n=s.size();·left=right=0;while(right<n){hash[s[right]]++;//进窗口while(hash[s[right]]>1){hash[s[left++]]--;//出窗口}ret=max(ret,right-left+1);//更新结果right++;}return ret==INT_MIN?0:ret;}
};

三.水果成蓝

3.1题目

• 题目：水果成蓝
  

3.2思路分析

3.3代码实现

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};//存储水果种类个数int ans=INT_MIN;for(int left=0,right=0,k=0,n=fruits.size();right<n;right++){if(hash[fruits[right]]==0)//进窗口{k++;//种类增加}hash[fruits[right]]++;//记录个数while(k>2){hash[fruits[left]]--;if(hash[fruits[left]]==0)//种类减少{k--;}left++;//出窗口}ans=max(ans,right-left+1);//更新结果}return ans;}
};

四.找到字符串中所有字母异位词

4.1题目

• 题目：找到字符串中所有字母异位词
  

4.2思路分析

4.3代码实现

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};int hash2[26]={0};for(auto a:p){hash1[a-'a']++;}int count=0;//记录有效字符个数for(int left=0,right=0,n=s.size();right<n;right++){char in=s[right];//进窗口if(++hash2[in-'a']<=hash1[in-'a']){count++;//有效字符增加}if(right-left+1>p.size()){char out=s[left++];//出窗口if(hash2[out-'a']--<=hash1[out-'a']){count--;//有效字符减少}}if(count==p.size()){ret.push_back(left);//保存结果}}return ret;}
};

五.串联所有单词的子串

5.1题目

• 题目：串联所有单词的子串
  

5.2思路分析

5.3代码实现

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map <string ,int> hash1;//字符串哈希表vector<int> ret;for(auto a:words){hash1[a]++;//填充哈希表存储单词个数}int len=words[0].size(),n=words.size();for(int i=0;i<len;i++){unordered_map <string ,int> hash2;for(int left=i,right=i,count=0;right+len<=s.size();right+=len){string in=s.substr(right,len);hash2[in]++;//填充哈希if(hash1.count(in)&&hash2[in]<=hash1[in])//判断是否有效字符串{count++;//更新有效单词个数}if(right-left+1>len*n)//出窗口{string out=s.substr(left,len);if(hash1.count(out)&&hash2[out]<=hash1[out])//判断是否有效字符串{count--;//更新有效单词个数}hash2[out]--;//更新哈希left+=len;}if(count==n){ret.push_back(left);//更新结果}}}return ret;}
};

算法总结

滑动窗口就是根据题目信息，在暴力枚举的条件下利用单调性优化，用同向双指针快速筛选掉一些不必要的遍历情况。在O(N)的复杂度下完成所有情况的枚举从而解题的算法。

后言

这就是滑动窗口算法原理的深度剖析。总而言之，滑动窗口就是在暴力枚举的情况下利用单调性，使用同向双指针在O(N)的复杂度完成枚举的算法。算法流程并不重要，重要的是背后的算法原理推到和证明。大家自己下去好好消化。今天就分享到，感谢各位的耐心垂阅！咱们下一期见！拜拜~