滑动窗口篇——如行云流水般的高效解法与智能之道（1）

前言：

上篇我们介绍了双指针算法，并结合具体题目进行了详细的运用讲解。本篇我们将会了解滑动窗口。滑动窗口是一种常用的算法技巧，主要用于处理子数组、子串等具有“窗口”特性的题目。柳暗花明，乃巧解复杂问题的高效之道。

一. 长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

题目分析：

1. 题目要求寻找一个子数组，数组内所有元素相加之和大于等于target，且要求该子数组的长度最小

2. 如果找到则返回最小子数组的长度，如果没有找到则返回0

注意：题目中所给的数组内所有元素均为正整数，且target也为正整数！！！ 

思路讲解：

暴力解法（会超时）：

滑动窗口：

暴力解法超时的原因为进行了大量冗余的遍历。

我们需要明白，由于所有的元素均为正整数，当子数组的区间长度在原有基础下增大时，和必然增大，反之，则必然减小，即子数组区间和的大小与区间长度存在单调性。

假设 target = 7, nums = [2, 3, 1, 2, 4, 3]：

初始状态：left = 0, right = 0, sum = 2，窗口未达到 target。
入窗口：将 right 向右移动，直到窗口和 sum = 9，满足条件。
出窗口：移动 left，将子数组 [4, 3] 缩小到长度 2。

因此，其解法可总结为入窗口，出窗口，更新情况三大步骤。

如图：

代码实现：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum=0;//子数组的和
        int n=nums.size(),ret=INT_MAX;//由于是求最小值，因此可首先假定其为int的最大值
        for(int left=0,right=0;right<n;right++)
        {
            sum+=nums[right];//进窗口
            while(sum>=target)
            {
                ret=min(ret,right-left+1);
                sum-=nums[left++];
            }//出窗口，更新ret，为下一轮遍历做准备
        }
        return ret==INT_MAX?0:ret;
        
    }
};

优势分析：

1. 时间复杂度为O(n)，远远优于暴力解法

2. 在处理重复遍历问题时，我们直接采取改变窗口区间长度的方式，利用先前分析过的单调性，以left和right对其进行控制，使效率大大提高。

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

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目分析：

1. 题目要求找出一个无重复长度的子串，且该子串要求长度最长。

2. 子串的含义同子数组类似，一定要求连续，最大可为字符串本身。

思路讲解： 

暴力解法（不会超时，可以通过）：

枚举「从每⼀个位置」开始往后，⽆重复字符的⼦串可以到达什么位置。找出其中⻓度最⼤的。

可在往后寻找⽆重复⼦串能到达的位置时，利⽤「哈希表」统计出字符出现的频次，来判断什么时候⼦串出现了重复元素。

代码实现：

class Solution {
public:
 int lengthOfLongestSubstring(string s) {
 int ret = 0; // 记录结果
 int n = s.length();
 // 1. 枚举从不同位置开始的最⻓重复⼦串
 // 枚举起始位置
 for (int i = 0; i < n; i++)
 {

 // 创建⼀个哈希表，统计频次
 int hash[128] = { 0 };
 
 // 寻找结束为⽌
 for (int j = i; j < n; j++)
 {
 hash[s[j]]++; // 统计字符出现的频次
 if (hash[s[j]] > 1) // 如果出现重复的
 break;
 
 // 如果没有重复，就更新 ret
 ret = max(ret, j - i + 1);
 }
 }
 // 2. 返回结果
 return ret;
 }
};

 滑动窗口：

研究的对象子串仍旧是一段连续的区间，因此可以考虑使用滑动窗口来解决。

1. 我们可以使用哈希来进行字符的映射，由于窗口内所有元素都是不重复的，因此我们可以让右端元素进入窗口，并记录其字符出现频次。

2. 当字符出现频次不全为0时，即代表出现了重复元素，需要让左侧元素逐次出窗口，直至恢复频次全为0为止。

3. 当完全遍历后，此时窗口长度即为最长字串的长度。

代码实现：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128]={0};//模拟哈希表
        int n=s.size();
        int ret=0;
        for(int left=0,right=0;right<n;right++)
        {
            hash[s[right]]++;//入窗口
            while(hash[s[right]]>1)
            {
                hash[s[left++]]--;//出窗口
            }
            ret=max(ret,right-left+1);//更新子串长度
        }
        return ret;
        
    }
};

 三. 最大连续1的个数lll

题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

题目分析：

1. 给定一个元素为1或0的数组，以及一个正整数K，可以在K的范围内把0变为1，求最长连续区间内均为1的长度。

2. 问题可转化为，求一段最长的连续区间，区间内0的个数在K范围内。

思路讲解：

滑动窗口：

此题仍为求一段连续区间的长度，因此也可以用滑动窗口来解决。

 1. 利用zere记录区间内0的个数，当zero小于K时，即可令右端元素进窗口

 2. 当zero>K时，需要令左端元素出窗口，如果左端元素为0，则令zero-1，直至zero<K为止。

3. 当完全遍历后，窗口长度即为最大连续区间的长度。 

代码实现：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int zero=0;//记录0的个数
        int n=nums.size(),ret=0;
        for(int left=0,right=0;right<n;right++)
        {
            if(nums[right]==0)
            {
                zero++;
            }//记录0的增长情况
            while(zero>k)
            {
                if(nums[left++]==0)
                {
                    zero--;
                }
            }//出窗口
            ret=max(ret,right-left+1);//更新窗口长度
        }
        return ret;
        
    }
};

小结：本篇介绍了滑动窗口的含义并结合基础题型加以讲解练习，下篇讲为大家分享滑动窗口的进阶题目，欢迎各位佬前来支持斧正！！！ 

 

原文地址：https://blog.csdn.net/2303_81060385/article/details/143957360

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！