【算法】滑动窗口—

【算法】滑动窗口——水果成篮

本篇博客是我对“水果成篮”这道题由暴力解法到滑动窗口思路的具体思路，有需要借鉴即可。

1.题目

题目链接：LINK

在这里插入图片描述

这道题，题干很长，大概意思是给你一个数组，然后你可以从随便一个数字开始依次遍历，直到遍历结束或者找到超过不同的两个数字，问你最大长度是几。

一般没有经验的人，肯定首先想到的是暴力求解，我也是一样哈，没啥经验。

2.暴力求解

那如何进行暴力求解呢？
暴力求解思路：哈希表 + 依次遍历

思路详解：具体来说，定义两个指针，一个left，一个right，再搞一个哈希表，right指向的数字就丢到哈希表里，计数，然后超过两个或者遍历结束的时候，我们更新一下结果然后left++，right = left，重新计数。然后这堆记的数字取个最大的就行了。

总而言之，代码如下：

class Solution {
public:
//暴力解法：
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int count = 0;
        int ret = 0;
        int sum = 0;
        for(int left = 0;left < n;left++)
        {
            count = 0;
            sum = 0;
            int hash[100001] = {0};
            for(int right = left;right < n;right++)
            {
                
                //进哈希表
                if(hash[fruits[right]] == 0)//一个新种类的水果
                {
                    hash[fruits[right]]++;
                    count++;
                    sum++;
                }
                else//这里标识之前有过的一个水果
                {
                    hash[fruits[right]]++;
                    sum++;
                }

                if(count > 2)
                {
                     ret = max(ret, sum - 1);break;
                }
               
                if(count <= 2 && right == n - 1)
                {ret = max(ret, sum);break;}
            }
        }

        return ret;
    }
};

然后不出意外哈，力扣绝对过不了，不然这题不会上中等难度了。

然后力扣提示说超出时间限制，比如下图：
在这里插入图片描述

所以说，这道题肯定是可以优化的，那具体怎么优化呢？我们一步一步来。

3.暴力优化

3.1每次right不用回退

这是什么意思呢？如下图所示：
在这里插入图片描述
在left固定的情况下，之后right这个地方数字种类超过2了，那么意思是红色这块区域数字种类个数是2，这时候按照暴力求解的方式，left++，right = left。

但是，我想说绿色的这块区域的数字种类会有可能超过2吗？显然这是不可能的，所以说right压根没有回去的必要。

3.2有些left长度一定不如前一个，不用走，left不回退

再比如说哈，如下图所示：
在这里插入图片描述
left = 2的情况下压根没必要去走好吧~~

行了，这时候我就发现这个题目经过优化之后满足“滑动窗口”的使用条件，两指针同向且不回退。

4.滑动窗口算法

然后可以直接优化成滑动窗口算法

class Solution 
{
public:
//滑动窗口：
    int totalFruit(vector<int>& fruits) {

        int n = fruits.size(), ret = 0,sum = 0,kands = 0;
        int hash[100001] = {0};//哈希数组

        for(int right = 0, left = 0;right < n;right++)
        {
            //进窗口
            if(hash[fruits[right]] == 0)kands++;//如果这个是一个新来的数，那么就种类++
            hash[fruits[right]]++;    
            sum++; 

            //出窗口
            while(kands > 2)
            {
                hash[fruits[left]]--;
                sum--;
                if(hash[fruits[left]] == 0)kands--;
                left++;
            }
           
           ret = max(ret, sum);
        }

        return ret;
    }
};