滑动窗口习题篇(上)
滑动窗口习题篇(上)
引言：
-
什么是滑动窗口——同向双指针
-
什么时候用滑动窗口——利用单调性
-
滑动窗口的正确性——利用单调性，规避了很多没有必要的枚举行为
-
滑动窗口的时间复杂度——O(N)
-
用滑动窗口如何书写代码，下列例题示范
1.长度最小的子数组
题目描述：
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其和
≥ target的长度最小的连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件子数组，返回 0 。示例 1：
输入：
target = 7, nums = [2,3,1,2,4,3] 输出：
2解释：
子数组
[4,3]是该条件下的长度最小的子数组。示例 2：
输入：
target = 4, nums = [1,4,4] 输出：
1示例 3：
输入：
target = 11, nums = [1,1,1,1,1,1,1,1] 输出：
0
解法一：暴力枚举出所有的子数组的和
算法思路：
1.从前往后枚举数组中的任意一个元素，把它当成起始位置。
2.然后从这个起始位置开始，然后寻找一段最短的区间，使得这段区间的和大于等于目标值。
3.在所有元素作为起始位置所得的结果中，找到最小区间值即可。
代码实现：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 记录结果
int ret = INT_MAX;
int n = nums.size();
// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
// 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩
// 枚举开始位置
for (int start = 0; start < n; start++)
{
int sum = 0; // 记录从这个位置开始的连续数组的和
// 寻找结束位置
for (int end = start; end < n; end++)
{
sum += nums[end]; // 将当前位置加上
if (sum >= target) // 当这段区间内的和满⾜条件时
{
// 更新结果，start 开头的最短区间已经找到
ret = min(ret, end - start + 1);
break;
}
}
}
// 返回最后结果
return ret == INT_MAX ? 0 : ret;
}
};
解法二：利用单调性，使用“同向双指针”来优化
“同向双指针”又称为滑动窗口
算法思路：
由于此问题分析的对象是一段连续的区间，因此可以考虑滑动窗口的思想来解决这道题。
1.进窗口判断条件：
从 i 位置开始，窗口内所有元素的和小于 target ；
滑动窗口做法：
left=0,right=0;
将右端元素划入窗口中，统计出此时窗口内元素的和(记为sum)：
如果sum<target： right++ ，使下一个元素进入窗口。（进窗口）
如果sum>= target ：更新结果，并且将左端元素划出去的同时继续判断是否满足条件并更新结果（因为左端元素可能很小，划出去之后依旧满足条件）（出窗口）
为何滑动窗可以解决问题，并且时间复杂度更低？
1.这个窗口寻找的是：从 left开始，满足 sum >= target 时，right能到哪里；
2.当right找到时，即找到了从 left开始的最优的区间，那么就可以大胆舍去当前 left ，进行left++。之后不必从++后的left进行重新统计，否则会由大量重复的计算；
3.就从当前right这个元素开始，往后找满足sum>=target的区间（当前right也有可能是满足的，因为++前的left可能很小，sum 剔除掉该left之后，依旧满足sum>=target ）；
4.这样就能省掉大量重复的计算，效率也会大大提升。
时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是 O(N) 。
代码实现：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size(),sum=0,len=INT_MAX;
for(int left=0,right=0;right<n;right++)
{
sum+=nums[right];//进窗口
while(sum>=target)
{
len=min(len,right-left+1);//更新结果
sum-=nums[left++];//出窗口
}
}
return len == INT_MAX?0:len;
}
};
2.无重复字符的最长子串
子数组：是数组中一个连续的部分
子串：是字符串中一个连续的部分
题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入:
s = "abcabcbb" 输出:
3 解释: 因为无重复字符的最长子串是
"abc"，所以其长度为3。示例 2:
输⼊:
s = "bbbbb" 输出:
1 解释: 因为无重复字符的最长子串是
"b"，所以其长度为1。示例 3:
输入:
s = "pwwkew" 输出:
3 解释: 因为无重复字符的最长子串是
"wke"，所以其长度为3。 请注意，你的答案必须是子串的长度，
"pwke"是一个子序列，不是子串。提示：
0 <=
s.length<= 5 * 104
s由英文字母、数字、符号和空格组成.
解法一：暴力枚举+哈希表（判断字符是否重复出现）O(N2)
算法思路：
枚举从每⼀个位置开始往后，无重复字符的子串可以到达什么位置。找出其中长度最大的即可。
在往后寻找无重复子串能到达的位置时，可以利用哈希表统计出字符出现的频次，来判断什么时候子串出现了重复元素。
代码实现：
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;
}
};
解法二：利用规律，使用“滑动窗口”来解决问题 O(N)
算法思路：
研究的对象依旧是一段连续的区间，因此继续使用滑动窗口思想来优化。
1.进窗口判断条件：
窗口内所有元素都是不重复的。
滑动窗口做法：
left=0,right=0;
右端元素 ch 进入窗口的时候，哈希表统计这个字符的频次：
- 如果这个字符出现的频次超过 1 ，说明窗口内有重复元素，那么就从左侧开始划出窗口（出窗口：从哈希表中删除该字符），直到 ch 这个元素的频次变为 1 ，然后再更新结果；
- 如果没有超过 1 ，说明当前窗口没有重复元素，可以直接更新结果，之后让下一个元素进入窗口（进窗口：让字符进入哈希表）。
代码实现：
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int hash[128]={0};//使用数组来模拟哈希表
int left=0,right=0,n=s.size();
int ret=0;
while(right<n)
{
hash[s[right]]++; //进入窗口
while(hash[s[right]]>1) //判断
hash[s[left++]]--; //出窗口
ret=max(ret,right-left+1); //更新结果
right++; //让下一个元素进入窗口
}
return ret;
}
};
3.最大连续 1 的个数 III
题目描述：
给定一个二进制数组
nums和一个整数k，如果可以翻转最多k个0，则返回数组中连续1的最大个数 。示例 1：
输如：
nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：
6解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。示例 2：
输入：
nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：
10解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
解法一：暴力枚举+zero计数器
解法二：滑动窗口 O(N)
算法思路：
不要去想怎么翻转，不要把问题想的很复杂，这道题的结果无非就是一段连续的 1 中间塞了 k个 0 嘛。
因此，我们可以把问题转化成：找出数组中最长的子数组，其中0的个数不超过k个。
既然是连续区间，可以考虑使用滑动窗口来解决问题。
1.进窗口判断条件：
子数组中0的个数不超过k个。
滑动窗口做法：
left = 0 ,right = 0 ,zero=0；
当
right<nums.size()，下列一直循环：
- 让当前元素进入窗口：如果是1，无视；如果是0，计数器
zero++；- 当
zero > k时：如果left所指是1，则无视；如果是0,计数器zero--、left++；- 更新结果：
ret=max(ret,right-left+1).
代码实现：
class Solution {
public:
int longestOnes(vector<int>& nums, int k)
{
int ret=0;
for(int left=0,right=0,zero=0;right<nums.size();right++)
{
if(nums[right]==0)
zero++;//进窗口
while(zero>k) //判断
if(nums[left++]==0)
zero--; // 出窗口
ret=max(ret,right-left+1); //更新结果
}
return ret;
}
};
4.将 x 减到 0 的最小操作数
题目描述：
给你一个整数数组
nums和一个整数x。每一次操作时，你应当移除数组nums最左边或最右边的元素，然后从x中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。如果可以将
x恰好 减到0，返回 最小操作数 ；否则，返回-1。示例 1：
输入：
nums = [1,1,4,2,3], x = 5 输出：
2解释：最佳解决方案是移除后两个元素，将
x减到0。示例 2：
输入：
nums = [5,6,7,8,9], x = 4 输出：
-1示例 3：
输入：
nums = [3,2,20,1,1,3], x = 10 输出：
5解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
提示：
1 <=
nums.length<= 1051 <=
nums[i]<= 1041 <=
x<= 109
正难则反
问题转化：找出最长的子数组的长度，所有的元素的和target正好等于sum-x
算法思路：
题目要求的是数组左端+右端两段连续的、和为 x 的最短数组，信息量稍微多⼀些，不易理清思路；
正难则反，我们可以转化成求最长的子数组的长度，所有的元素的和target正好等于sum-x
此时，就是熟悉的滑动窗口问题了。
算法流程：
1.进窗口判断条件：
target==sum-x
滑动窗口做法：
- left = 0 ,right = 0 ,tmp=0；
- 当前滑动窗口内数组和的变量记为sum=0;
- 当
right<nums.size()，下列一直循环：
如果
tmp<target,tmp+=nums[right]（进窗口）,right++,直至tmp>targetor right越界；如果
tmp>target,tmp-=nums[left]（出窗口）,left++,直至tmp<targetor left越界；当经过前两步的左右移动使得
tmp == target，更新结果
- 如果
target<0，返回-1.
代码实现：
class Solution
{
public:
int minOperations(vector<int>& nums, int x)
{
int sum = 0;
for(int a : nums)
sum += a;
int target = sum - x;
// 细节问题
if(target < 0)
return -1;
int ret = -1;
for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
{
tmp += nums[right]; // 进窗⼝
while(tmp > target) // 判断
tmp -= nums[left++]; // 出窗⼝
if(tmp == target) // 更新结果
ret = max(ret, right - left + 1);
}
if(ret == -1)
return ret;
else
return nums.size() - ret;
}
};
时间复杂度为O(N).
最后，本篇文章到此结束，感觉不错的友友们可以一键三连支持一下笔者，有任何问题欢迎在评论区留言哦~