当前位置：首页 > news >正文

D2力扣滑动窗口系列

news 来源：原创 2024/5/20 13:19:16

滑动窗口算法（Sliding Window）：

滑动窗口算法（Sliding Window）：在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

滑动操作：窗口可按照一定方向进行移动。最常见的是向右侧移动。
缩放操作：对于不定长度的窗口，可以从左侧缩小窗口长度，也可以从右侧增大窗口长度。

滑动窗口利用了双指针中的快慢指针技巧，我们可以将滑动窗口看做是快慢指针两个指针中间的区间，也可以将滑动窗口看做是快慢指针的一种特殊形式。

适用范围&题型：

滑动窗口算法一般用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。该算法可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

按照窗口长度的固定情况，我们可以将滑动窗口题目分为以下两种：

固定长度窗口：窗口大小是固定的。
不定长度窗口：窗口大小是不固定的。
- 求解最大的满足条件的窗口。
- 求解最小的满足条件的窗口。

不定长度滑动窗口算法

不定长度滑动窗口算法（Sliding Window）：在给定数组 / 字符串上维护一个不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

算法步骤：

使用两个指针left、right。初始时，left、right都指向序列的第一个元素。即：left=right=0;
区间[left,right]被称为一个「窗口」。将区间最右侧元素添加入窗口中，即 window.add(s[right])。
然后向右移动 right++，从而增大窗口长度，直到窗口中的连续元素满足要求。此时，停止增加窗口大小。
转向不断将左侧元素移出窗口，即 window.popleft(s[left])。
然后向右移动left++，从而缩小窗口长度。直到窗口中的连续元素不再满足要求。

时间复杂度： $0\left ( n \right )$ 。

例题：

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

这道题目典型的求不定长度窗口的题。（字符串的子串一般使用滑动窗口）

本题解答：遍历字符串，如果字符没出现过，就放到窗口中，即right++，出现过，就把他（包含前面的）扔出窗口即left--；

关于字符串是否出现过有两种解法。

方法一：建立数组 bool hash[256],出现过就1，没有出现过就0；

class Solution {//不定滑动窗口大小
public:int lengthOfLongestSubstring(string s) {if(s.size()==0) return 0;int left=0;int right=0;//定义滑动窗口指针bool hash[256]={0};//定义字母数组,用来判断字母是否出现过，如果字母出现过为1，没出现过为0;int maxl=0;int len=0;while(right<s.size()){if(hash[s[right]]==0){//元素未出现过hash[s[right]]=1;right++;len++;}else{//出现过hash[s[left]]=0;left++;len--; }maxl=max(maxl,len);}return maxl;}
};

方法二：使用 unordered_set（）无需字符集合。

huadong.find(s[i])!=huadong.end()//s[i]存在
huadong.insert(s[i])//插入元素
huadong.erase(s[i])//删除元素

class Solution {//滑动窗口
//大题思想：遍历s中的元素，如果不在滑动窗口中重复，就加入窗口（此时，窗口长度会增大）。如果重复，就从窗口中删除元素（此时窗口长度减少，开始位置后移）。
public:int lengthOfLongestSubstring(string s) {int maxl=0;//maxl最大值;if(s.size()==0) return 0;//创建无序字符集合，保存滑动窗口unordered_set<char> huadong;int start=0;//滑动窗口的startfor(int i=0;i<s.size();i++){while(huadong.find(s[i])!=huadong.end()){//当前字符s[i]在集合 huadong中已经存在 huadong.erase(s[start]);//将其删除，滑动窗口的起始位置后移start++;}maxl=max(maxl,i-start+1);huadong.insert(s[i]);}return maxl;}
};

时间复杂度： $0\left ( n \right )$ 。

类似题目：

209. 长度最小的子数组

大体思路：

eg. nums = [2,3,1,2,4,3]

将元素一直往窗口里面放，当sum>target时，往外扔元素。

为什么可以一直往里面放元素呢？首先一开始sum<target,肯定可以往里放，后面>的时候，进入while循环，一旦while结束，必定又＜，并且这样能实现right++，从而跳出循环。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0;int right=0;int sum=0;int ans=INT_MAX;while(right<nums.size()){sum+=nums[right];while(sum>=target){ans=min(ans,right-left+1);sum-=nums[left];left++;}right++;}return ans== INT_MAX ? 0 : ans;}
};

时间复杂度： $0\left ( n \right )$ 。空间复杂度： $0\left ( 1 \right )$

类似题目：

713. 乘积小于K的子数组 - 力扣（LeetCode）

固定长度滑动窗口算法：

固定长度滑动窗口算法（Fixed Length Sliding Window）：在给定数组 / 字符串上维护一个固定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

算法思想：

假设窗口的固定大小为 window_size。使用两个指针 left、right。
初始时，left、right 都指向序列的第一个元素，即：left、right=0
区间 [left,right]被称为一个「窗口」。当窗口未达到 window_size 大小时，不断移动right，即right++。
先将数组前 window_size个元素填入窗口中，即 window.append(nums[right])。当窗口达到 window_size 大小时，即满足 right - left + 1 >= window_size 时，
判断窗口内的连续元素是否满足题目限定的条件。如果满足，再根据要求更新最优解。然后向右移动 left，从而缩小窗口长度，即 left += 1，使得窗口大小始终保持为 window_size。向右移动 right，将元素填入窗口中，即 window.append(nums[right])。重复上述步骤，直到right 到达数组末尾

例题:

1343. 大小为 K 且平均值大于等于阈值的子数组数目

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

数组题目一定注意越界情况

解法一：仍然使用双指针。

这里要注意先算sum，再进行right++，否则会出现越界情况

class Solution {
public:int numOfSubarrays(vector<int>& arr, int k, int threshold) {int left=0;int right=0;int ans=0;int sum=0;//float avg;求出它们的元素和，如果这个和大于等于threshold*k，那么就说明其平均值大于等于threshold了。//这样处理可以不用涉及除法运算，避免引入浮点数，效率更高。//vector<int> window;while(right<k){//先加入k个元素// window.push_back(arr[right]);sum+=arr[right++];}if(sum>=threshold*k)//判断前k个元素的和是否满足。ans++;while(right<arr.size()){//先运算避免后面越界sum+=arr[right++]-arr[left++];//下一个k个元素和if(sum>=threshold*k)ans++;         }      return ans;}
};

int sum=0;//float avg;求出它们的元素和，如果这个和大于等于threshold*k，那么就说明其平均值大于等于threshold了。
//这样处理可以不用涉及除法运算，避免引入浮点数，效率更高。

改进一下：其实left与 right的距离相同，可以直接不用变换left，直接用right-left+1来判断

class Solution {
public:int numOfSubarrays(vector<int>& arr, int k, int threshold) {int left=0;int right=0;int ans=0;int sum=0;//float avg;求出它们的元素和，如果这个和大于等于threshold*k，那么就说明其平均值大于等于threshold了。//这样处理可以不用涉及除法运算，避免引入浮点数，效率更高。//vector<int> window;while(right<k){// window.push_back(arr[right]);sum+=arr[right++];}while(right<arr.size()){if(sum>=threshold*k) ans++; sum += arr[right] - arr[right - k];right++;}if(sum>=threshold*k)ans++; return ans;}
};

类似题目：1052. 爱生气的书店老板