算法篇：滑动窗口

使用范围此方法针对的对象是一段连续的区间。做题模板区分子数组/子串、子序列、子集子数组/子串是原数组中连续的一段区间要求保持顺序也要求连续。子序列是原数组中删除若干元素后剩下的序列不要求保持顺序要求连续。子集是从原来集合中任意选取一些元素不要求保持顺序也不要求连续。举例说明对于数组 [1, 2, 3, 4]子数组[1,2]、[2,3,4]、[3]、[1,2,3,4]注意[1,3] 不是子数组不连续子序列[1,3]、[2,4]、[1,2,4]、[1,2,3,4]注意[2,1] 不是子序列顺序改变子集{1,3}、{2,4}、{1,2,4}、{1,2,3,4}注意{2,1} 和 {1,2} 是同一个子集顺序无关题目实例长度最小的子数组209. 长度最小的子数组 - 力扣LeetCode子数组为一段连续的区间可以考虑用滑动窗口的方法解答这个问题。解题思路该题目需要我们找的是总和大于等于target的最小长度的子序列。根据总和我们可以定义一个sum变量来实现进窗口当加到总和大于等于target的时候可以进行更新结果最后在出窗口进行后面数组的判断。class Solution { public: int minSubArrayLen(int target, vectorint nums) { int left0,right0; int nnums.size(); int sum0,minlenINT_MAX; for(;rightn;right) { sumnums[right]; while(sumtarget) { minlenmin(minlen,right-left1); sum-nums[left]; left; } } return minlenINT_MAX?0:minlen; } };注时间复杂度虽然代码是两层循环但是我们的 left 指针和 right 指针都是不回退的两者最多都往后移动 n 次。因此时间复杂度是 O(N) 。无重复字符的最长子串3. 无重复字符的最长子串 - 力扣LeetCode子串为一段连续的区间可以考虑用滑动窗口的方法解答这个问题。解题思路哈希表滑动窗口记得维护哈希表右端元素进入窗口时用哈希表统计元素个数根据题意:不含重复的字符这表明这段连续区间内每个元素都只有一个那么我们就可以得到我们出窗口的条件只要有一个元素在这段区间内超过1了就对该区间进行出窗口直到该区间内无重复元素时对它进行更新结果。class Solution { public: int lengthOfLongestSubstring(string s) { int hash[128]{0}; int left0,right0; int maxlen0; for(;rights.size();right) { char chs[right]; hash[ch]; while(hash[ch]1) { char rets[left]; hash[ret]--; left; } maxlenmax(maxlen,right-left1); } return maxlen; } };当只有小写字母或者大写字母时哈希表只用hash[26];当不止一种且都是ASCII中的元素时哈希表用hash[128]。最大连续 1 的个数 III1004. 最大连续1的个数 III - 力扣LeetCode根据题意求取在一段区间内把里面的k个0变成1后数组中连续1的最大个数即求取连续区间内最大个数的1k的最大个数。解题思路用一个变量count来统计0在区间内出现的个数根据题目最多可以反转k个0可以得出出窗口的条件countk,在出窗口的时候记得维护count变量。出窗口后更新结果。class Solution { public: int longestOnes(vectorint nums, int k) { int count0; int left0,right0; int maxnum0; for(;rightnums.size();right) { //for循环中right已经是进窗口了 if(nums[right]0) { count; } //出窗口 while(countk) { if(nums[left]0) { count--; } left; } //更新结果 maxnummax(maxnum,right-left1); } return maxnum; } };将 x 减到 0 的最小操作数1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode题意移除最左边或最右边的数使移除的数等于x转换思维题目中移除的是最右边或最左边的数是不是只要保证中间的区域只要等于全部数的总和-x就行了所以我们就转换求结果等于sum-x的最长子数组最后用总长减最长子数组即可。解题思路根据思路我们可以在数组中找一段连续的区间等于sum-x即可解题方法如第一道题一样相当于这个题目的targetsum-x但是更新结果和出窗口的位置不一样。这题是要在总和等于sum-x的时候更新结果而出窗口的提交条件是区间中的和加起来大于target所以不能在出窗口的时候更新结果出完窗口后我们才能更新结果。细节问题这里我们求的是最长的子数组但是定义最长子数组长度的值不能初始化为0因为当数组中全部数都大于x的时候最长子数组的长度为0而整个数组的和为x的时候最长子数组长度的和也为0但是第一种输出的结果为-1第二个输出的是数组的长度。class Solution { public: int minOperations(vectorint nums, int x) { //求取中间连续区间的值等于总和-x long long sum0; for(auto s:nums) { sums; } if(sumx) { return -1; } int left0,right0; int maxnum-1; long long ret0; long long targetsum-x; for(;rightnums.size();right) { retnums[right]; while(rettarget) { //出窗口 ret-nums[left]; left; } if(rettarget) maxnummax(maxnum,right-left1); } return maxnum-1?-1:nums.size()-maxnum; } };水果成篮904. 水果成篮 - 力扣LeetCode题意解析一共有两个篮子每个篮子只能放同一种水果也就是数组中数字一样的例如fruits [1,2,3,2,2] 这个数组中有三种水果分别是123.解题思路哈希表滑动窗口进窗口把右端的值放入到哈希表中哈希表中统计每个水果的个数。出窗口题目中的限制条件是两个篮子那么两个篮子就可以设置成出窗口的条件。更新结果更新最大数目哈希表可以用两种形式的unordered_mapint,inthash,int hash[100001]{0};如果用unordered_map这种容器的哈希表记得元素的个数为0的时候要删除元素。int totalFruit(vectorint fruits) { unordered_mapint,inthash; int left0,right0,nfruits.size(); int maxlen-1; for(;rightn;right) { hash[fruits[right]]; while(hash.size()2) { //出窗口 hash[fruits[left]]--; if(hash[fruits[left]]0) { hash.erase(fruits[left]); } left; } maxlenmax(maxlen,right-left1); } return maxlen; } };class Solution { public: int totalFruit(vectorint fruits) { int hash[100001]{0}; int left0,right0,nfruits.size(); int maxlen-1; int count0;//水果的种类 for(;rightn;right) { if(hash[fruits[right]]0) { count; } while(count2) { //出窗口 hash[fruits[left]]--; if(hash[fruits[left]]0) { count--; } left; } maxlenmax(maxlen,right-left1); } return maxlen; } };找到字符串中所有字母异位词438. 找到字符串中所有字母异位词 - 力扣LeetCode求的是子串子串是一段连续的区间可以考虑滑动窗口。解题思路哈希滑动定义一个变量来统计在s中有多少符合p个数的字符串count还定义两个哈希表一个哈希表hash1来统计p中所有个数一个哈希表hash2来统计s中所有个数,这三个变量都是在接下来的解题中需要维护的。进窗口把s中的字符统计的同时维护count变量统计有多少个符合p个数的字符串可以通过hash2[s[right]]hash1[s[right]]统计。出窗口如果用countright-left1来作为出窗口的条件的话那么就只是表明在这个数组中right-left1这一段里面没有连续的符合p的子串而且这个条件也不能判断count是不是等于p.size()所以这个不能作为判断条件。判断要和p的大小有关而且要符合长度所以用right-left1p.size()作为判断条件。出窗口时我们要维护count变量hash2变量和left变量。更新结果判断条件countp.size()class Solution { public: vectorint findAnagrams(string s, string p) { //哈希滑动 unordered_mapchar,inthash1; unordered_mapchar,inthash2; vectorint result; for(auto s:p) { hash1[s]; } int left0,right0; int count0;//符合的个数 for(;rights.size();right) { char chs[right]; if(hash2[ch]hash1[ch])count; while(right-left1p.size()) { //出窗口 char is[left]; if(hash2[i]--hash1[i])count--; left; } if(countp.size()) { result.push_back(left); } } return result; } };串联所有单词的子串30. 串联所有单词的子串 - 力扣LeetCode题意解析找到数组中一段包含words中所有单词的连续区间单词的顺序可以任意。连续区间可以考虑用滑动窗口。关键信息words中所有字符串长度一样。解题思路把数组分割成words中单词长度的大小但是我们怎么知道要从哪里开始分割才能遇到words中的单词呢这时候我们就需要一个循环这里可以优化但我们循环超过words字符串长度一样的时候发现和从0开始遍历的单词是一样的了所以我们可以缩小循环次数在单词长度之间。这题上题解题类似只是把字符看成字符串就行。细节部分count的变量应该放在循环里遍历字符串s的哈希表也要放在循环里不然哈希表每次遍历都不是新的结果。class Solution { public: vectorint findSubstring(string s, vectorstring words) { unordered_mapstring, int hash1; vectorint result; for (auto s : words) { hash1[s]; } int left 0, right 0; int m words[0].size(); for (int i 0; i m; i) { int count 0; unordered_mapstring, int hash2; for (righti,lefti; right s.size(); right m) { string rs s.substr(right, m); if (hash2[rs] hash1[rs]) { count; } while (right - left 1 m * words.size()) { string ls s.substr(left, m); if (hash2[ls]-- hash1[ls]) { count--; } left m; } if(words.size()count) { result.push_back(left); } } } return result; } };最小覆盖子串76. 最小覆盖子串 - 力扣LeetCode题目解析寻找一段连续区间中只要包含t中所有的字符的最短子串即最短子串中可以存在其他字符但是一定要全部包含t中所有的字符。解题思路和找到字符串中所有字母异位词的解题思路一样但是这题要求的是返回字符串。进窗口遍历右端元素进入哈希表出窗口根据题意寻找的是最短的子串那么也就是说最好最后一个结尾的就是t元素中包含的全部字符的最后一个字符所以这里的出窗口的条件就是当区间内刚好countt.size()。这个时候就是刚好符合题目的要求所以我们要在出窗口前更新结果而题目返回的是字符串那么我们可以通过string容器中的substr函数来进行结果返回sustr有两个参数一个是起始位置一个是截取多少个字符所以我们要定义两个变量来记录。细节部分begin设置为-1记录子串起始位置的值返回的时候要对begin进行判断。class Solution { public: string minWindow(string s, string t) { unordered_mapchar,inthash1; for(autoch:t) { hash1[ch]; } int left0,right0; int minlenINT_MAX; int count0; int begin-1; unordered_mapchar,inthash2; for(;rights.size();right) { if(hash2[s[right]]hash1[s[right]])count; //出窗口 while(countt.size()) { if(minlenright-left1) { minlenmin(minlen,right-left1); beginleft; } if(hash2[s[left]]--hash1[s[left]])count--; left; } } if(begin-1) return ; else return s.substr(begin,minlen); } };