优选算法---专题2(滑动窗口)

209. 长度最小的子数组 - 力扣LeetCode对于任何一道题如果一开始没思路的话都是从暴力解法开始入手然后再去优化。对于本题暴力解法就是枚举出所有的子数组然后选取其中满足条件的并且还要是最短的那个。两层for循环有一个优化的点边枚举边定义一个sum变量统计和满足情况就直接返回j后边的数字都不用考虑因为数组全是正整数越加越大找到一个满足条件之后再后边的肯定都满足但是长度肯定比当前这个长。虽然上述暴力解法也稍微优化了一下但依旧不够得继续优化下述的优化就是同向双指针也叫滑动窗口一般在区间出现单调性且双指针不回退的情况下用到这个算法最重要的就是双指针要不回退就可以用这个算法了。本质就是对暴力双层循环的优化算法。具体滑动窗口的使用就是差不多包含5步骤初始化双指针进窗口判断窗口是否合法出窗口更新结果其中更新结果和出窗口谁前谁后具体问题具体分析。class Solution { public: int minSubArrayLen(int target, vectorint nums) { long long l 0, r 0; long long n nums.size(); long long sum 0; long long ret 1e7 10;//ret设置为本题数据范围的最大值方便后边取min int flag 0; while(r n) { //进窗口 sum nums[r]; while(sum target) { //更新结果出窗口 flag 1; ret min(r - l 1, ret); sum - nums[l]; } r; } //如果一个都没有满足的返回ret即返回的是1e710但题目意思是返回0 //所以设置flag来看看是否区间被修改 if(!flag) return 0; return ret; } };3. 无重复字符的最长子串 - 力扣LeetCode首先想到的肯定是暴力解法将全部的不重复子区间都枚举出来比出最长的那一个。暴力解法显而易见就是O(N^2)的时间复杂度优化的点也很显然每次l的时候r有必要回退吗很显然没必要l之前把l位置的元素从我们的容器里删除即可然后l得到的新的[l, r]区间就直接用就可以了没必要r再回退重新计算所以本题也是拿双指针去优化。最后一个问题就是怎么判断区间里是否出现了重复的元素很简单用map记录一下元素出现的次数次数1就说明该val重复了。一旦想到双指针算法就是去想5个点初始化进窗口判断窗口是否合法出窗口更新结果。class Solution { public: int lengthOfLongestSubstring(string s) { int n s.size(); int l 0, r 0; mapchar, int mp;//字符次数 int ret -1e7 10; while(r n) { //进窗口 mp[s[r]]; //判断合法性 while(mp[s[r]] 1) { //出窗口 --mp[s[l]]; l; } ret max(ret, r - l 1); r; } return ret -1e7 10 ? 0 : ret; } };1004. 最大连续1的个数 III - 力扣LeetCode根据题目意思本题可以转化为寻找数组中最长的一段子数组其中0的个数不超过k个。我们可以用一个变量zero去记录当前区间里0的个数只要不超过k个就是合法区间。因此暴力解法诞生通过下图的分析可以用同向双指针去优化。class Solution { public: int longestOnes(vectorint nums, int k) { int n nums.size(); int l 0, r 0, zero 0; int ret -1e7; while(r n) { //进窗口 if(nums[r] 0) zero; //判断合法 while(zero k) { if(nums[l] 0) --zero; l; } //更新结果根据示例一画画图就知道了 ret max(ret, r - l 1); r; } return ret; } };1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode定义一前以后两个指针分别指向数组的开头和结束判断开头和结束的两个数字谁的值与x的差值小就将x减去这个数字这样可以保证x做减法的次数是最少的但很遗憾经过代码验证这种贪心策略是错误的。其实本题难就难在不知道选择到底是左边还是右边的数去被x减去正难则反我们可以从反面去考虑这个问题本题的意思不就是找到左边一段区间和右边一段区间使得左右区间的和等于x并且这个左右区间必须是符合要求的最短区间因为它要求返回的是最小操作数。反过来就是在中间找到一段最长的区间使得这个区间的和等于sum-xsum表示数组里所有元素的和即找出最长的子数组的长度使得子数组里所有元素的和等于sum-x最后将区间总长度减去这个最长区间的长度不就是答案了。问题转换后首先想到的暴力解就是找出全部满足里头所有元素之和等于sum-x的区间然后比出最长的那个就可以了。优化不就是可以用同向双指针吗因为指针不用回退每找到一个符合条件的区间的时候l之前仅需将原区间里的和扣掉nums[l]即为当前新区间的和就不用让r回退重复计算了。因为[l, r]是刚好sum-x的区间则[l, r - 1]这段区间必定是sum-x的那l之后r不用回退因为l之后的[l, r - 1]区间比之前的[l, r - 1]区间之和还要小就更不可能sum-x了因为数组里全是正数就导致有上边的单调性所以r只能往后走不用回退。class Solution { public: int minOperations(vectorint nums, int x) { int sum 0; for(auto e : nums) sum e; if(sum x) return -1; sum - x; int n nums.size(); int l 0, r 0; int len -1e7;//表示区间长度 int sm 0; while(r n) { //进窗口 sm nums[r]; //判断窗口是否合法 while(sm sum) sm - nums[l]; //更新结果---必须要判断一下smsum //不然会产生一种情况就是smnums[r]直接就sum了没有的环节 //上述情况也不是我们想要的 if(sm sum) len max(len, r - l 1); r; } return len -1e7 ? -1 : n - len; } };904. 水果成篮 - 力扣LeetCode本题的意思就是在数组里找一段最长的区间里边仅只能包含两种类型的数字。首先想到暴力解法枚举出所有的仅包含两种类型数的区间比比谁最长即可如何知道这段区间里有几种类型的数字呢定义一个变量kind用map去记录每个数字出现的次数如果数字的次数从0-1则kind从1-0则kind--。用同向双指针去优化r不用回退因为l之后仅需将map里数字的次数--并且判断kind是多少即可不用r回到l的位置继续重新统计。注如果说本题数据范围过大超出int范围则可以不用kind直接当mp[fruits[l]]--为0的时候mp.erase(fruits[l])即可。class Solution { public: int totalFruit(vectorint fruits) { int n fruits.size(); int l 0, r 0; mapint, int mp; int kind 0, ret -1e7; while(r n) { int t1 fruits[r]; //进窗口 if(mp[t1] 0) { kind; } //判断是否合法 while(kind 2) { int t2 fruits[l]; //出窗口 if(mp[t2]-- 1) { --kind; } l; } //更新结果 ret max(ret, r - l 1); r; } return ret; } };438. 找到字符串中所有字母异位词 - 力扣LeetCode异位词就是两个字符串里的单词的种类以及个数一样但顺序不一样的字符串比如说abc和cba。在统计异位词个数之前先想想怎么判断两个字符串是否是异位词第一种想法就是排序便利看看每一个位置的字符是否相同但是时间复杂度过高nlognn。第二种想法是利用哈希表统计出字符串里每一个字符出现的次数然后便利一遍哈希表跟p字符串里去比较如果每一个字符出现的次数一样就说明是异位词。暴力解法假设p字符串长度为m先将p里的字符次数统计在一个哈希表里然后以每m长度的字符串为一组去便利便利的过程中顺便将每一个字符出现的次数全部统计下来最后便利一下哈希表比对一下两个哈希表里的数据。class Solution { public: vectorint findAnagrams(string s, string p) { //题目里说仅包含26个小写字母 int hashp[26] {0}; for(auto e : p) hashp[e - a]; vectorint ret; int l 0, r 0; int hashs[26] {0}; while(r s.size()) { //进窗口 hashs[s[r] - a]; r; //判断窗口是否合法 while(r - l p.size()) { //出窗口 --hashs[s[l] - a]; l; } if(r - l p.size()) { int flag 0; //更新结果---便利哈希表一遍 for(int i 0;i 26;i) { if(hashs[i] ! hashp[i]) { flag 1; break; } } if(!flag) { ret.push_back(l); } } } return ret; } };这里说一下如果用的unordered_map那么上述的代码其实没有改变很多唯一一个就是判断两个哈希表是否相等时容器内部是重载了!运算符的就不用手动便利了。一旦确定是同向双指针一定按照5个步骤来写代码不然逻辑混乱很容易死循环。