行业知识
算法之滑动窗口
题目1:209. 长度最小的子数组 - 力扣(LeetCode)
��解法⼀(暴力求解):
思路:
从前往后, 枚举数组中的任意⼀个元素, 把它当成起始位置, 然后从这个起始位置开始, 然
后寻找⼀段最短的区间, 使得这段区间的和「⼤于等于」⽬标值.
将所有元素作为起始位置所得的结果中, 找到最⼩值即可。
解法⼆(滑动窗⼝):
思路:
由于此问题分析的对象是⼀段连续的区间, 因此可以考虑滑动窗⼝的思想来解决这道题.
这道题我们不妨换一个角度思考, 我们先不去思考怎么去针对这个最短区间做文章, 而是讨论每个下标i作为窗口的左端的情况下能取得的最短窗口长度, 在窗口缩短的过程中不断地更新这个最短长度, 最后的长度就是最短长度.
那怎么去求得这个最短长度呢?
1. 将右端元素划⼊窗⼝中(right++), 统计出此时窗⼝内元素的和:
如果窗⼝内元素之和sum⼤于等于 target : 更新长度len, 并且将左端元素划出去(left++), 更新sum, 为什么可以直接把最左端元素划出窗口?
因为此时窗口内的sum已经是以left为起始的最短满足条件的子数组了, 算上right之后的数窗口只会更长, 所以left为起点的这一组就判断完了.
2. left划出窗口后, 如果当前窗口的sum比target小, 肯定right要继续++, 但是当前窗口的sum也可能大于等于target, 所以应该继续判断sum去决定right是不是要继续++, 那此时是应该继续划出窗口呢? 还是right回退到left重新算一遍窗口内的sum呢?
right不需要再回退到left重新来算一遍sum了, 抛开right对应的值, 此时窗口内的和肯定比上一个窗口小, 所以当前窗口以left为起点的子窗口的sum肯定更小, 所以right在上次的位置待着即可.
此时区间内的和要么是小于target的, 继续right++; 要么是大于等于target的, 也就是当前最小的一种子数组, 继续重复之前的步骤即可
可以注意到过程中left和right都是同向移动的, 这样的同向双指针称为滑动窗口:
为何滑动窗⼝可以解决问题, 并且时间复杂度更低?
▪ 这个窗⼝寻找的是: 以当前窗⼝最左侧元素(记为left1 )为基准, 符合条件的情况.也就是在这道题中, 从left1开始, 满⾜区间和sum >= target 时的最右侧(记为right1 )能到哪⾥.
▪ 我们既然已经找到从 left1 开始的最优的区间, 那么就可以⼤胆舍去left1,但是如果继续像⽅法⼀⼀样,重新开始统计第⼆个元素(left2)往后的和, 势必会有⼤量重复的计算(因为我们在求第⼀段区间的时候, 已经算出很多元素的和了, 这些和是可以在计算下次区间和的时候⽤上的).
▪ 此时, rigth1 的作⽤就体现出来了, 我们只需将 left1 这个值从 sum 中剔除, 从right1这个元素开始, 往后找满⾜left2元素的区间(此时right1也有可能是满⾜的, 因为left1可能很⼩, sum 剔除掉left1之后, 依旧满⾜⼤于等于target ), 这样我们就能省掉⼤量重复的计算。
▪ 这样我们不仅能解决问题, ⽽且效率也会⼤⼤提升。
时间复杂度:虽然代码是两层循环,但是left指针和 right指针都是不回退的, 两者最多都往后移动n次, 因此时间复杂度是? O(N)
class Solution {public: int minSubArrayLen(int target, vector& nums) { int left = 0, right = 0, n = nums.size(); int sum = 0, len = INT_MAX; while(right = target) { //更新最小长度 int newlen = right - left + 1; len = len
题目2:3. 无重复字符的最长子串 - 力扣(LeetCode)
解法⼀(暴⼒求解):
思路:
枚举「从每⼀个位置」开始往后, ⽆重复字符的⼦串可以到达什么位置, 找出其中⻓度最⼤的即可.在往后寻找⽆重复⼦串能到达的位置时, 可以利⽤「哈希表」统计出字符出现的频次, 来判断什么时候⼦串出现了重复元素.
解法⼆(滑动窗⼝):
思路:
研究的对象依旧是⼀段连续的区间, 因此继续使⽤「滑动窗⼝」思想来优化,
让滑动窗⼝满⾜: 窗⼝内所有元素都是不重复的。
做法:右端元素 ch 进⼊窗⼝的时候, 哈希表统计这个字符的频次.
▪ 如果这个字符出现的频次超过 1 , 说明窗⼝内有重复元素, 那么就从左侧开始划出窗⼝, 直到ch这个元素的频次变为1, 然后再更新结果, 因为left要跳过当前right指的重复元素, 才有机会得到新的最长子串, 否则每次都会被right卡***, 长度始终无法突破最开始的长度.
▪ 如果没有超过1, 说明当前窗⼝没有重复元素, 可以直接更新结果.
class Solution {public: int lengthOfLongestSubstring(string s) { map m; int left = 0,right =0; int len = 0; while(right 1) m[s[left++]]--;//左边一直滑动,直到跳过重复字符 len = max(len,right - left + 1);//更新长度 right++;//向右滑动窗口 } return len; }};
题目3:1004. 最大连续1的个数 III - 力扣(LeetCode)
解法(滑动窗⼝):
思路:
不要去想怎么翻转, 这道题的结果⽆⾮就是⼀段连续的 1 中间塞了k 个0 , 因此, 我们可以把问题转化成:求数组中⼀段最⻓的连续区间, 要求这段区间内 0 的个数不超过 k 个.
既然是连续区间, 可以考虑使⽤滑动窗⼝来解决问题.
写法1:
class Solution {public: int longestOnes(vector& nums, int k) { int left = 0, right = 0; int zerocount = 0; int len = 0; while(right 写法2:
class Solution{public: int longestOnes(vector& nums, int k) { int ret = 0; for(int left = 0, right = 0, zero = 0; right k) // 判断 if(nums[left++] == 0) zero--; // 出窗⼝ ret = max(ret, right - left + 1); // 更新结果 } return ret; } };
题目4:1658. 将 x 减到 0 的最小操作数 - 力扣(LeetCode)
解法(滑动窗⼝):
思路:
题⽬要求的是数组「左端+右端」两段连续的和为 x 的最短数组, 信息量稍微多⼀些,不易理清
思路, 正难则反, 我们可以转化成求数组内⼀段连续的和为sum(nums) - x的最⻓数组。此时, 就是滑动窗⼝问题.
class Solution {public: int minOperations(vector& nums, int x) { int left = 0, right = 0; int n = nums.size(); int sumi = 0, len = -1; int sum = 0; for(auto& e: nums) sum += e; while(right sum - x) sumi -= nums[left++]; if(sumi == sum - x) len = max(len, right-left+1); right++; } if(len == -1) return -1; return nums.size() - len; }};
题目5:904. 水果成篮 - 力扣(LeetCode)
解法(滑动窗⼝):
思路:
研究的对象是⼀段连续的区间, 可以使⽤滑动窗⼝思想来解决问题, 让滑动窗⼝满⾜:窗⼝内⽔果的种类只有两种.
做法: 右端⽔果进⼊窗⼝的时候, ⽤哈希表统计这个⽔果的频次, 这个⽔果进来后, 判断哈希表的
大小:
▪ 如果大小超过2: 说明窗⼝内⽔果种类超过了两种, 先记录结果然后出窗口, 从左侧开始依次将⽔果划出窗口直到哈希表的大小小于等于2, 然后更新结果;
▪ 如果没有超过2, 说明当前窗⼝内⽔果的种类不超过两种, 继续统计.
while循环:
class Solution {public: int totalFruit(vector& fruits) { unordered_map m; int left = 0, right = 0, n = fruits.size(), ret = 0; while(right 2) { if(--m[fruits[left]] == 0) m.erase(fruits[left]); left++; } ret = max(ret, right - left); } return ret; }}; 参考别人的for循环实现:
class Solution {public: int totalFruit(vector& fruits) { int hash[100001] = {0}; int ret = 0; for(int left=0,right=0,kinds=0; right 2) { hash[fruits[left]]--; if(hash[fruits[left]] == 0)//如果kinds减为0种类-- kinds--; left++; } ret = max(ret,right-left+1); } return ret; }};
题目6:438. 找到字符串中所有字母异位词 - 力扣(LeetCode)
判断异位词只需要创建两个字母的哈希表, 如果哈希表相同, 那么这两个串就是异位词, 对于这题来说, 可以考虑用哈希表是否相等来判断异位词, 大思路还是滑动窗口, 而且这是一个定长的滑动窗口, 同样还是分为入窗口, 判断, 出窗口, 更新结果这几个步骤:
class Solution {public: bool isEqual(int* h1, int* h2) { for(int i = 0;i m)//判断 { hash1[s[left++]-'a']--;//出窗口 } if(isEqual(hash1,hash2)) ret.push_back(left); right++; } return ret; }}; 但是判断哈希表是否相等的代价有点大了, 这题还好, 如果需要判断的是字符串等自定义类型的哈希表, 那代价就很大了, 所以考虑进行优化更新结果的判断条件:
利用一个变量count来统计窗口中有效字符的个数, 我们全程只需要去移动滑动窗口的同时去维护这个count, 通过比较count是否和p的长度相等, 即可判断是否是字母异位词:
如何去判断一个字符是否有效呢?
如果 hash1[s[right]-'a']
上一篇:哪里可以买到云服务器配件?
下一篇:小米购买华为服务器怎么用?