商业空间设计案例ppt/seo推广排名公司

在双指针的技巧中，有一类比较特殊的技巧，通过滑动左右指针来求解问题。

虽然我们上一篇也提到过一些通过left和right移动来求解的问题。
双指针的配合

但滑动窗口这类问题更多的会固定一边滑动另一边，这个更像窗口的大小改变，所以叫做滑动窗口。

数组滑动

先来看几道数组滑动的题目，感受滑动窗口的较为固定的模式。

leetcode 209 长度最小的子数组

给定一个数组，找到和大于等于target的长度最小的连续子数组。

因为是连续子数组，所以可以用两个指针来滑动。

滑动窗口的核心

用一个例子来了解滑动窗口的核心动作：

比如数组[2,3,1,2,4,3]，我们定义left指针和right指针都在起始位置(2)，然后right往右走来扩大边界，[2],[2,3],[2,3,1],[2,3,1,2]，这个窗口不断扩大。

什么时候停止扩大右边界呢？

当满足题目条件时。

这道题中就是在和大于等于target的时候，我们就可以停止right，开始缩小窗口了。

这时候我们先把[2,3,1,2]这个结果记下来，再寻找下一个结果。

缩小窗口，left开始移动，变成了[3,1,2]，发现又不满足条件了，那么left就可以休息了。

right继续工作，再扩大，[3,1,2,4]，发现可以满足了，记录下来，然后left继续缩小窗口。

[1,2,4]，依旧满足，记录下来，继续缩小。

[2,4]，不满足了，left休息right工作，扩大为[2,4,3]，记录下来。

left继续缩小，[4,3]，也满足，记录下来。

最后在所有记录里面找到最短的即可。

int minSubArrayLen(int target, vector<int>& nums) {int left=0;int right=0; int sum=0; //求和int result=INT32_MAX;//因为要求最短的，所以设定初始为最大while(right<nums.size()){//向右扩大窗口sum+=nums[right];right++;while(sum>=target){//满足条件做记录，然后缩小窗口result=result<(right-left)?result:(right-left);sum-=nums[left];left++;}}return result==INT32_MAX?0:result;}

这是滑动窗口一种比较经典的模板。要注意如果right++写在while循环的最后，那么长度就应该是right-left+1

当然这个长度具体是多少要看我们需要的数组包不包括right这一位，也就是左闭右开和左闭右闭的区别。

巩固练习

还有一道滑动窗口的题目

leetocde 904 水果成篮

这道题可以翻译为求只包含两种元素的最长连续子数组。

比如[1,2,3,2,2]，答案就是[2,3,2,2]。

我们用滑动窗口来解决这个问题，在遇到第三种元素时就记录前面这个子数组的长度，然后再重新选择两种元素，继续扩大窗口。

先看代码：

int totalFruit(vector<int>& fruits) {int left=0,right=0;int f1=fruits[left],f2=fruits[right];int maxLength=0;while(right<fruits.size()){if(fruits[right]!=f1&&fruits[right]!=f2){//遇到第三种元素maxLength=maxLength>(right-left)?maxLength:(right-left);left=right-1;f1=fruits[left];f2=fruits[right];while(left>=1&&fruits[left-1]==f1){left--;}}right++;}return maxLength>(right-left)?maxLength:(right-left);

首先设定两种元素为fruits[left]和fruits[right]，如果遇到第三种元素，就记录长度。

这里最核心的做法是让 left=right-1，即left指向right的前一位。这样可以快速定位两种元素的位置。

如果left前面还有与它相等的元素，那么再让left–去将它们包含进来。

我们用例子来快速理解一下：比如[3,3,3,1,1,2,2,1,1,2]

• 首先fruits[left]和fruits[right]都是3，所以在遇到1的时候就要记录长度，并且移动left。

• 这时候才是真正定义两种元素的开始，f1是3，f2是1。并且left回退到了起始位置，包含了所有的3。

• 当遇到2时，记录前面序列[3,3,3,1,1]的长度，然后left指向[3,3,3,1,1]的最后一个1，同时回退去包含前面一个1

• 一直移动到结尾，序列就变为[1,1,2,2,1,1,2]

需要注意：

• 为什么right++在记录长度之后，长度却还是right-left？这就和上题所说的一样，当我们遇到第三种元素时，right已经不在这个序列中了，相当于左闭右开，所以不需要+1
• 最后为什么不是直接返回maxLength？因为right最后可能会退出循环，但并未保存最后一次的结果。例子中就是这样的。
  
  

字符串滑动

最小覆盖子串

滑动窗口最经典的一道hard题目，就是最小覆盖子串

leetcode 76 最小覆盖子串

是要在给定的子串s中寻找包含t的最短子串。

比如s=ADOBECODEBANC，t=ABC，那么最短的就是BANC

其实这道题本质上还是左右边界的移动。我们可以根据这个例子简单理解这个过程：

• 首先left和right都指向左边，然后right开始移动。
• 移动到什么时候停止呢？**在这个窗口包含所有t的字符时。**这时就可以记录长度了。
• left开始移动，left什么时候停止呢？在不包含t的所有字符时（这里容易产生歧义，比如t是ABC，那么在不包含任意一个的时候left就会停止），然后继续移动right
• 这种模式和我们开篇说的“left在满足条件时移动，不满足时停止”是一致的。
• 最后取最短的即可。

代码看上去很长，但非常有规律。

string minWindow(string s, string t) {int left=0;//左指针int right=0;//右指针//需要最小长度和起点，才能调用substr取子串int minLength=INT32_MAX;//int start=0;//当一个字符匹配成功且数量达到needs的要求就让match+1int match=0;unordered_map<char,int>window;unordered_map<char,int>needs;for(char c:t)//初始化needsneeds[c]++;while(right<s.size()){char c1=s[right];if(needs.count(c1)){//如果needs中有c1，那么就让window对应+1window[c1]++;if(window[c1]==needs[c1])//当一个字符完全匹配后，match+1match++;}right++;while(match==needs.size()){//当字符都匹配后，right停止，开始动left缩小窗口if (right - left < minLength) {//取较小的值start = left;minLength = right - left;}char c2=s[left];if(needs.count(c2)){//如果needs中有c2，那么window将c2移出。当不满足条件时，left就不动了。开始动right。window[c2]--;if(window[c2]<needs[c2]){match--;}  }left++;} }return minLength==INT32_MAX?"":s.substr(start,minLength);//取最小子串}

我们需要维护两个unordered_map，一个是用来记录t中字符的needs，另一个是用来匹配的window。

window虽说是窗口，但是实际使用的时候我们只去匹配t中有的字符，其余字符就直接忽略，让right++就好。

windows的匹配过程是分为两层的：

• 第一层是遇到字符就记录下来，但是t中有可能有重复字符，所以需要多次记录
• 如果某一个字符的数量符合needs中要求的数量，那么这个字符就匹配成功，对应的match就加1
• 直到match符合needs的长度时，才包含了所有的字符。

这种解法很巧妙，建议全文理解。

找到字符串中所有字母异位词

leetocde 438 找到字符串中所有字母异位词

这道题给字母的排列取了一个高端的名字，字母异位词。

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

其实就是在s中找到p的排列，然后返回他们的起始下标。

继续使用滑动窗口：

vector<int> findAnagrams(string s, string p) {int left=0;int right=0;int match=0;vector<int>res;unordered_map<char,int>window;unordered_map<char,int>needs;for(char c:p)needs[c]++;while(right<s.size()){char c1=s[right];if(needs.count(c1)){window[c1]++;if(window[c1]==needs[c1]){match++;}}right++;while(match==needs.size()){if((right-left)==p.size())//只有这里有区别，条件的区别。res.push_back(left);char c2=s[left];left++;if(needs.count(c2)){window[c2]--;if(window[c2]<needs[c2]){match--;}}}}return res;}

因为和上题中的解法一致，所以就不写注释了，如果明白上题那么这道题就很简单了。

字符串的排列

leetcode 567 字符串的排列

如果s1的排列之一是s2的子串，那么返回true

和上一题也是比较相似的。甚至更简单。只要有一个排列就可以返回true了

继续滑动：

 bool checkInclusion(string s1, string s2) {int left=0;int right=0;int match=0;unordered_map<char,int>window;unordered_map<char,int>needs;for(char c:s1)needs[c]++;while(right<s2.size()){char c1=s2[right];if(needs.count(c1)){window[c1]++;if(window[c1]==needs[c1]){match++;}}right++;while(match==needs.size()){if(right-left==s1.size()){//长度符合直接返回return true;}char c2=s2[left];if(needs.count(c2)){window[c2]--;if(window[c2]<needs[c2]){match--;}  }left++;}}return false;}

还是一致的，只是到达条件处的一点点区别。