2024年11月13日练习（滑动窗口算法）

一.904. 水果成篮 - 力扣（LeetCode）

      1.题目解析：

            

其实这个题目的意思就是在这个数组里面找一个连续的最长字数组，这个最长的子数组最多只能包

含两种数字。

      2.算法原理：

              方法一：

                就是暴力解法把所有符合情况的子数组列举出来，然后找出最长的那个子数组。

               如图：

               

在暴力解法中我们肉眼可以直接看出我们刚刚列举的数组里面的元素出现了几次，但是在写代码的

过程中，我们借助一个数组，当出现一次就把这个出现的数字丢进这个数组，然后再去检查下一个

元素时，如果这个元素在数组里面出现一次，那就++，再去检查下一个元素，如果数组里面的元

素种类超过了2种，那么就不符合了。 

           方法二：

          现在来优化一下暴力解法，我们直接拿一个横线表示一个任意的数组：

     

假设此时right已经向后遍历，找到了最适合的位置，那么就是right再向后移动时，这个区间已经不

符合要求了，那么此时这个区间里面的水果种类就等于2。

如果是暴力解法时，left++，然后right回来向后继续枚举：

但是此时left++后有两种情况，第一种就是kind不变还是等于2，那么如果不变，在暴力解法中

right还要回来往后走，但是还是走到这个位置，此时其实就没有必要往回走了。第二种就是kind

变小，right也没有必要回来，可以继续往后走，寻找新的种类，扩大数组的长度：

那么此时两个指针向同一方向走，我们这里就用滑动窗口算法即可：

3.代码展示：

    

class Solution {
public:
    int totalFruit(vector<int>& f) {
        int arry[100001]={0};//统计窗口出现了多少种水果
        int ret=0;
        for(int left=0,right=0,kind=0;right<f.size();right++){
            if(arry[f[right]]==0){//检查水果种类
                kind++;
            }
            arry[f[right]]++;//进窗口
            while(kind>2){
                //出窗口
                arry[f[left]]--;
                if(arry[f[left]]==0){
                    kind--;
                }
                left++;
            }
            ret=max(ret,right-left+1);
        }
        return ret;
    }
};

原文地址：https://blog.csdn.net/2301_81154519/article/details/143745458

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！