滑动窗口篇——如行云流水般的高效解法与智能之道（2）

前言：

上篇我们介绍了滑动窗口的含义并结合基础题型加以练习，本篇将以进阶难度的题目为索引，深化对于滑动窗口的运用与理解。

一. 将x减到0的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

题目分析：

1. 题目要求我们每次只能从最左侧或最右侧来进行删除，且要求在原数组上直接进行修改，以满足后续操作。

2. 如果元素之和和恰好等于x，则返回最小操作数，如果不存在满足情况，则返回-1.

3. 题中提到数组内每个元素都为正整数，但target的大小不确定。

思路讲解：

该题的困难之处在于感到无从下手，每次操作为左侧还是右侧的不确定性，采用遍历时的恐怖时间复杂度，都让我们苦不堪言。

这时，不妨采取正难则反的思路。

1, 我们令数组内每个元素相加，和为sum，题目的要求可转化为求一段最长的连续区间，满足和为sum-x。

2. 转化之后，则可根据连续区间的性质，利用滑动窗口求解。

滑动窗口：

我们定义flag为数组内所有元素相加之后减去x的值，那么问题已然转化为求一段最长的连续区间，满足和与flag相等，也就是我们熟悉的滑动窗口。

1. 进窗口：由于此时每一个元素都大于0，所以在窗口内增加元素，总和必然增大，因此在sum<flag时，right保持++即可，在总和sum与flag相等时，更新区间长度。

2. 出窗口：当sum>flag时，说明区间过长，此时left++即可，避免大量冗余遍历。

注意：我们在第一节谈到滑动窗口的核心三步骤为进窗口，出窗口，更新情况。

三者并无严格的先后关系，需要根据实际情况灵活运用！！！

代码实现：

class Solution {
public:int minOperations(vector<int>& nums, int x) {int flag=0,sum=0,len=-1;int n=nums.size();for(auto e:nums){flag+=e;}//所有元素相加if(flag<x){return -1;}//不存在符合情况flag-=x;//求取连续区间之和需满足的值for(int left=0,right=0;right<n;right++){sum+=nums[right];//进窗口while(sum>flag){sum-=nums[left++];}//出窗口if(sum==flag){len=max(len,right-left+1);}//更新情况}if(len==-1){return -1;}//没有满足的情况else{return n-len;}}
};

注意：如果不判定flag<x的情况，则会陷入死循环，因为此时flag为负数，while循环内left会一直++。

二. 水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

题目分析：

题目较长，我们先理解给出了哪些条件和题目所求是什么：

1. 有一个数组，每一个元素的值代表水果种类

2. 有两个篮子，只能取两种类型的水果，每一棵树最多只能取一个水果。

3. 当遇到与两个篮子类型都不同的水果时，需要立即停止。反之则可以继续一直往后遍历采集

4. 求可以采摘的最多水果数。

下面我们来具体分析：

1. 水果种类匹配问题，不难想到采用哈希映射

2. 采摘过程也是一个连续的区间，且也满足单调性，在该种情况下，如果向右采摘成功，水果总数必然增加，因此可以考虑在控制好种类匹配的基础上，使用滑动窗口进行解决。

思路讲解：

滑动窗口需满足，窗口内的水果种类数只有两种。

1. 采用哈希表记录水果的种类和数量，在种类小于2时，right侧可继续往后遍历，进窗口。

2. 当种类大于2时，left侧需要向后遍历出窗口，如果该水果对应的哈希表等于0时，代表种类减少了一种，需要及时改变记录。

流程如下：

a. 初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量；
b. 初始化变量：左右指针 left = 0，right = 0，记录结果的变量 ret = 0；
c. 当 right ⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
i. 将当前⽔果放⼊哈希表中；
ii. 判断当前⽔果进来后，哈希表的⼤⼩：
• 如果超过 2：
◦ 将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；
◦ 如果这个元素的频次减⼀之后变成了 0，就把该元素从哈希表中删除；
◦ 重复上述两个过程，直到哈希表中的⼤⼩不超过 2；
iii. 更新结果 ret；
iv. right++，让下⼀个元素进⼊窗⼝；
d. 循环结束后，ret 存的就是最终结果

代码实现：

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};//模拟哈希int kind=0;//记录水果种类int nums=0;//记录水果个数for(int left=0,right=0;right<fruits.size();right++){if(hash[fruits[right]]==0){kind++;}//增加水果种类hash[fruits[right]]++;//进窗口while(kind>2){hash[fruits[left]]--;//出窗口if(hash[fruits[left]]==0){kind--;}//更新水果种类left++;//更新left}nums=max(nums,right-left+1);//更新水果个数}return nums;}
};

小结：