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

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

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

🔥专栏：算法笔记

前言

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

一.长度最小的子数组

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)的复杂度完成枚举的算法。算法流程并不重要，重要的是背后的算法原理推到和证明。大家自己下去好好消化。今天就分享到，感谢各位的耐心垂阅！咱们下一期见！拜拜~