【优选算法篇】--深度解析之滑动窗口篇

一、长度最小的子数组

长度最小的子数组

解析：

首先看到这题 我们首先想到的是暴力枚举，就是暴力枚举所有子数组和。时间复杂度是O(n^3)。

我们这里用解法二，利用单调性，使用“同向双指针”，（也叫滑动窗口）定义俩指针left right 让他们同向移动。left标记窗口的左区间，right标记窗口的右区间。首先进窗口，然后判断是否出窗口。
让右边的指针先走，走的过程要维护下窗口，用sum记录下每走一步的区间和。如果和小于target，我们就不出窗口（因为我们要找个最佳位置，也就是大于target位置）。大于target我们就出窗口（出窗口的时候我们要记录下此时窗口的长度，方便后续更新），出窗口left右移动，sum减去那个值，然后再判断。最后直到找到最小的长度。

草图如下：

---

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size(),sum=0,len=INT_MAX;for(int left=0,right=0;right<n;right++){//进窗口sum+=nums[right];while(sum>=target)//判断{len=min(len,right-left+1);//更新结果sum-=nums[left++];//出窗口}}return len==INT_MAX?0:len;}
};

---

二、无重复字符的最长子串

无重复字符的最长子串

解析：
看到求最长子串，我们可能首先会想到暴力枚举，枚举每一个字符 然后判断是否出现过，这里我们可以用到哈希表来判断是否出现过。但是暴力枚举的过程中，碰到一个重复字符，又得返回来。然而我们有个更优的解法。滑动窗口配上哈希表。

我们定义left,right等于起始位置，先进窗口（这里今后窗口意思就是让字符进入哈希表），一直向后走，走到某一个位置发现有重复的字符，那就让这个right先固定到这个位置不动，让left向后走，一直走到跳过跟right重复的字符（也就是出窗口，出窗口要让哈希表里的值减少）。然后这个right继续才能向后走，如果又碰到重复的字符，重复left指针操作（也就是继续向后移动， 走到跳过跟right相同的字符位置）

---

草图如下：

---

代码：

class Solution {
public:int lengthOfLongestSubstring(string s) {int left=0,right=0,n=s.size();int hash[128]={0};//数组模拟哈希表，下表对应是字符，里面的值对应这个字符出现了多少次。int ret=0;while(right<n){hash[s[right]]++;//进窗口while(hash[s[right]]>1){//出窗口hash[s[left++]]--;//哈希表值减少，然后做指针向右移动}ret=max(ret,right-left+1);right++;}return ret;}
};

---

三、最大连续1的个数III

最大连续1的个数

解法：
题目要求我们反转k个0，返回数组中连续1的最大个数。也就是将k个0翻转后，使得数组中连续1的个数最大。
其实我们可以将问题转换下，转换成找最长子数组，0的个数不超过K个。返回结果就是这个子数组长度。

我们在解题过程中，要注意进窗口，出窗口。我们right向右走的时候，如果zero（记录区间0的个数）大于k，left向右走，走到哪里呢，走到0的位置此时zero–，也就是出窗口。此时记录下区间长度。继续循环，直到找到最长子数组。

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret=0;for(int left=0,right=0,zero=0;right<nums.size();right++){if(nums[right]==0)  zero++;//进窗口while(zero>k)//判断if(nums[left++]==0)//出窗口，left碰见0，--;zero--;ret=max(ret,right-left+1);}return ret;}
};

---

四、水果成篮

水果成蓝
题目描述：
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

• 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
  给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

---

解析：

• 题目意思其实就是找一块连续最长子数组，里面字多两种水果。顾名思义，其实就是，找一块最长子数组，里面数字的类型不超过两种。

• 这里讲解下思路。使用滑动窗口，配上哈希表。就能解决问题。left 和 right 分别表示满足要求的窗口的左右边界，同时我们使用哈希表存储这个窗口内的数种类以及出现的次数。

• 我们每次将 right 移动一个位置，并将 fruits[right] 加入哈希表，加入过程中如果使得哈希表长度大于2，说明这个窗口里面数字的类型超过了两种，此时我们就要出窗口，判断操作。出窗口fruits[left]移除。需要注意的是，将 fruits[left] 从哈希表中移除后，如果 fruits[left] 在哈希表中的出现次数减少为 0，需要将对应的键值对从哈希表中移除。

• 什么意思呢，我们以下面这张图里面的示例为例说明下吧，如果我们走到3，窗口里已经尝过了两种，此时我们left向后走，走到不出现1的位置，也就是标红色的地方。1这个数字就没有了，我们需要将它从哈希表中移除，也就是erase。

---

草图如下：

---

代码：

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int,int>hash;//<种类，数量>int ret=0,left=0,right=0,n=fruits.size();while(right<n){hash[fruits[right]]++;//进窗口//判断，出窗口while(hash.size()>2){hash[fruits[left]]--;//得判断下，因为水果种类超过了俩个，left向后移动得删除一个种类if(hash[fruits[left]]==0){hash.erase(fruits[left]);}left++;}ret=max(ret,right-left+1);right++;}return ret;}
};