1.Leetcode209.长度最小的子数组2. Leetcode3.无重复字符的最长子串3.Leetcode1004.最大连续1的个数 III4.Leetcode1658.将 x 减到 0 的最小操作数5.Leetcode904.水果成篮6.Leetcode438.找到字符串中所有字母异位词7.Leetcode30.串联所有单词的子串8.Leetcode76.最小覆盖子串9.滑动窗口总结做题规律使用滑动窗口的场景我们需要利用同向双指针我们发现暴力解答需要利用单调性时可以使用滑动窗口。先利用两个指针代表左端点和右端点。然后按照进窗口判断出窗口的循环开始使用这里有个更新结果的操作这个更新可以放在进窗口判断出窗口三个位置。这里本质是利用单调性规避了没有必要的枚举行为才实现其正确性时间复杂度要具体代码具体分析可能代码上有两层循环但时间复杂度是On1.Leetcode209.长度最小的子数组209. 长度最小的子​​​​​​数组class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(), sum 0, len INT_MAX;//len不能定义为0不然、len一直为0 for (int left 0, right 0; right n; right) { sum nums[right]; while (sum target) { len min(len, right - left 1); sum - nums[left]; left; } } return len INT_MAX ? 0 : len; } };解析这道题我们可以先想出用暴力枚举的方法也就是把所有target的所有情况都列出来然后选出最短的。再此方法上我们可以进一步优化我们可以利用left,right两个“指针”进行遍历但right不用像暴力解法一样返回它只需一直向前而left的移动方向和right一致。这就是同向双指针的滑动窗口的用法。因此我们可以设置指针都为0让right向右移动当left和right之间的值target就更新一次长度的结果让后left向右移动直至right到达最后一个数据。这里我们在设置结果的初始长度时不能设置0不然就找不到正确的最小子数组。因此可以用INT_MAX初始化无论第一结果为多少都进行更新2. Leetcode3.无重复字符的最长子串3. 无重复字符的最长子串class Solution { public: int lengthOfLongestSubstring(string s) { int n s.size(), len 0; int hash[128] { 0 };//使用数组模拟哈希表 for (int left 0, right 0; right n; right) { hash[s[right]];//进入窗口 while (hash[s[right]] 1) { hash[s[left]]--; left; } len max(len, right - left 1); } return len; } };解析先想出暴力枚举的方法就是列举出所有情况然后选出不含重复字符的最长子串。然后我们再此基础上可以进行优化这里我们可以使用哈希表的性质进行答题这里我们可以利用left和right两个同向的指针。用right来让这个元素在哈希表中初始化然后right。当right这个地方的值在哈希表中出现次数1就移动left让这个次数减小到1。然后在每次哈希表正常时更新结果。因为这里的数据大小是ASCll标准字符个数为128所以我们可以利用一个数组充当哈希表不需要使用unordered_map。3.Leetcode1004.最大连续1的个数 III1004. 最大连续1的个数 IIIclass Solution { public: int longestOnes(vectorint nums, int k) { int zero0,len0,nnums.size(); for(int left0,right0;rightn;right) { if(nums[right]0) zero; while(zerok) if(nums[left]0) zero--; lenmax(len,right-left1); } return len; } };解析通过题目我们可以题目转化为找出最长的子数组并要求0的个数不超过k个先想出暴力枚举的方法还是罗列出所有情况找出最长的数组。接下来我们就可以优化了首先还是利用滑动窗口的方法用left和right记录right遍历数组然后right每到一个0就用zero变量记录0的数量。直至zerok时此时我们就要移动left让zerok。每次判断之后就用len记录结果。4.Leetcode1658.将 x 减到 0 的最小操作数1658. 将 x 减到 0 的最小操作数解析这里我们如果想按照题目的方式进行做题就非常困难因为我们无法控制每次取左边还是右边。因此正向做题困难我们就反过来。就是取出所有值之和减去x的值(sum-x)当我们找到这个值之后就返回它的长度然后用总长度减去这个长度就是最终的结果。还是同向双指针的滑动窗口利用left和right让right遍历数组求出每个值之和当这个值之和等于sum-x就返回right-left1。然后求出这个值的最大值。最终返回用总长度-这个值。结果就是最小操作数。这里我们在初始化len最长符合sum-x的值时把它初始化为-1找不到符合sum-x的值就返回-15.Leetcode904.水果成篮904. 水果成篮class Solution { public: int totalFruit(vectorint f) { unordered_map int, int hash; int ret 0; for (int left 0, right 0; right f.size(); right) { hash[f[right]]; while (hash.size() 2) { hash[f[left]]--; if (hash[f[left]] 0) hash.erase(f[left]); left; } ret max(ret, right - left 1); } return ret; } }; //用数组 class Solution { public: int totalFruit(vectorint f) { int hash[100001] {0}; int ret 0; int len 0; for (int left 0, right 0; right f.size(); right) { if(hash[f[right]]0) len; while (len 2) { hash[f[left]]--; if (hash[f[left]] 0) len--; left; } ret max(ret, right - left 1); } return ret; } };解析先理解题目题目就是让我们找出两种水果按照题目通俗点讲就是两种数字但这两种数字的个数没有限制只有种类的限制。先想出暴力枚举的方法把所有符合情况到找到然后返回最大数目的值。还是利用哈希表来记录数字的种类然后利用滑动窗口left和right。right遍历数组每找出一种数字哈希表中该数字就然后当哈希表中数字种类2时就要移动left让数字种类2。然后每次判断后就取出最大的数量。直至right遍历结束后就返回出最大的数量。这里我们可以直接利用哈希表也可以利用数组模拟哈希表。它们的区别在于利用数组时我们还需要一个变量记录数字的种类而用哈希表就直接利用size函数求出种类。6.Leetcode438.找到字符串中所有字母异位词438. 找到字符串中所有字母异位词class Solution{ public: vectorint findAnagrams(string s, string p) { vectorint ret; int m p.size(); int hash1[26] {0}; int hash2[26] {0}; for (auto s : p) hash2[s - a]; for (int left 0,right 0,count 0; right s.size(); right) { char in s[right]; hash1[in - a]; if (hash1[in - a] hash2[in - a]) count; if (right - left 1 m) { char out s[left]; if (hash1[out - a] hash2[out - a]) count--; hash1[out - a]--; } } return ret; } };解析先理解题目就是在s中找到p中的数据连续顺序可以不同个数和种类都要相同。然后看返回结果我们就需要一个vector容器记录返回结果。因此还是利用哈希表的性质记录数据的个数不过这里是两个哈希表第一个哈希表直接编辑记录p的数量第二个哈希表记录s不过第二个哈希表是用right遍历数组记录当两个哈希表相同时就用retvector容器记录结果这里当s的个数p的个数时就要移动left去让两个都个数相同再次判断种类是否相同。这里的数据都是小写字母一共有26个所以可以直接用两个数组模拟哈希表这里我们需要注意只有两个哈希表的个数和种类都相同时才更新结果。利用一个变量记录是否记录结果。7.Leetcode30.串联所有单词的子串30. 串联所有单词的子串class Solution { public: vectorint findSubstring(string s, vectorstring w) { vectorint ret; unordered_mapstring,int hash1; for(auto s: w) { hash1[s]; } int lenw[0].size(),mw.size(); for(int i0;ilen;i) { unordered_mapstring,int hash2; for(int lefti,righti,count0;rightlens.size();rightlen) { string ins.substr(right,len); hash2[in]; if(hash1.count(in)hash2[in]hash1[in]) count; if(right-left1len*m) { string outs.substr(left,len); if(hash1.count(out)hash2[out]hash1[out]) count--; hash2[out]--; leftlen; } if(countm) ret.push_back(left); } } return ret; } };解析这道题的逻辑和上一道找出字符串中所有字符异位词差不多不过这个words中记录的是一个一个字符串然后找出s中数量和种类相同的首下标这里的顺序不能改变。这里words中字符串的长度都相同这就使我们用right遍历数组时移动长度不再是1而是words中的长度。这里第一层的循环是为了防止有些字符存在顺序不能但最终个数和种类相同。这里通过输出我们还要用一个vector记录输出结果这里还是利用两个哈希表来记录s中是否存在words中的字符串。不过这里需要双层循环也就是left和right位置需要改变第一层循环记录每一个的位置这个循环次数还是取决于words的长度。第二层循环记录left和right的移动情况。这里为了优化结构我们可以用count变量记录两个words的每个字符串在s中存在的个数当countwords的个数就用vector记录数据的首下标。这里hash1.count(in)和hash1.count(out)是为了把不属于words中的情况去除节约了时间只计算属于words中的情况让count8.Leetcode76.最小覆盖子串76. 最小覆盖子串class Solution { public: string minWindow(string s, string t) { int hash1[128]{0}; int kins0; for(auto s:t) { if(hash1[s]0)kins ; hash1[s]; } int hash2[128]{0}; int minlenINT_MAX,begin-1; for(int left0,right0,count0;rights.size();right) { char ins[right]; hash2[in]; if(hash2[in]hash1[in]) count; while(countkins) { if(right-left1minlen) { minlenright-left1; beginleft; } char outs[left]; if(hash1[out]hash2[out]) count--; hash2[out]--; } } if(begin-1) return ; else return s.substr(begin,minlen); } };解析先了解题目这里我们需要在s中找到t中字符的子串只要求存在不要求顺序和位置。还是先想暴力枚举一个一个枚举数据然后用哈希表记录数据出现次数当两个哈希表相同时就可以更新结果。在此基础上我们开始优化先用两个数组模拟哈希表因为这里都是英文字母。然后我们用滑动窗口的同向双指针left和right用right遍历数组让其在哈希表中初始化。先让t中的所有数据直接通过范围for进行初始化然后我们利用变量kins记录数据种类当s中存在t中的元素count就当countkins时就可以存最小的字符串了首先用minlen更新此时的长度begin记录起始位置此时我们就可以尝试缩短字符串长度看能不能继续缩短最终长度此时出数据当出现两个哈希表相同时count就--。当countkins时就进行下一次right的遍历。直至right遍历完数组结果也更新完。这里初始化begin为-1是为了当s中不存在t中的数据时就直接返回空字符串存在就返回该字符串。而初始化minlen为INT_MAX初始化不能初始化0不然就无法更新最小长度了9.滑动窗口总结做题规律滑动窗口的底层逻辑不难就4步1.进窗口2.判断3.出窗口4.更新数据它可出现在判断和出窗口的任意位置但为什么这样做就是我们要思考的内容了过程无非4步其中的各种遍历和边界情况才是我们要思考的内容如何进窗口如何判断如何出窗口如何更新结果如何优化都是我们要思考的问题。这里的底层是我们在使用时是同向双指针不能是异向的