滑动窗口算法详解：水果成篮问题解法

水果成篮

题目描述：

给定一个整数数组 fruits，其中 fruits[i] 表示第 i 棵树上的水果种类。你拥有两个篮子，每个篮子只能装一种类型的水果。你需要选择连续的树来采摘水果，使得采摘的水果种类不超过两种。返回你可以采摘的最大水果数量。

题目示例：

输入：[1,2,1] 输出：3 解释：可以采摘所有三棵树上的水果。

解法（滑动窗口）：

算法思路：

研究的对象是一段连续的区间，可以使用【滑动窗口】思想来解决问题。

让滑动窗口满足：窗口内水果的种类只有两种。

做法：右端水果进入窗口的时候，用哈希表统计这个水果的频次。这个水果进来后，判断哈希表的大小：

• 如果大小超过 2：说明窗口内水果种类超过了两种。那么就从最左侧开始依次将水果划出窗口，直到哈希表的大小小于 2，然后更新结果；
• 如果没有超过 2，说明当前窗口内水果的种类不超过两种，直接更新结果。

算法流程：

1. 初始化哈希表 hash 来统计窗口内水果的种类和数量；
2. 初始化变量：左右指针 left=0，right=0，记录结果的变量 ret=0；
3. 当 right 小于数组大小的时候，一直执行下列循环：
   • 将当前水果放入哈希表
   • 判断当前水果进来后，哈希表的大小：
     • 如果超过 2：
       • 将左侧元素滑出窗口，并且在哈希表中将该元素的频次减一；
       • 如果这个元素的频次减一之后变成了 0，就把该元素从哈希表中删除；
       • 重复上述两个过程，直到哈希表中的大小不超过 2；
   • 更新结果 ret；
   • right++，让下一个元素进入窗口；
4. 循环结束后，ret 存的就是最终结果。

C++代码演示（数组模拟哈希表）：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 数据范围有限可以使用数组模拟哈希表
        int hash[100001] = {0};
        int n = fruits.size();
        int left = 0, right = 0, kinds = 0, len = 0;
        
        while (right < n) {
            if (hash[fruits[right]] == 0) kinds++; // 维护水果种类
            hash[fruits[right]]++;                 
            
             (kinds > ) {                    
                hash[fruits[left]]--;              
                 (hash[fruits[left]] == ) kinds--;
                left++;
            }
            
            
            len = (len, right - left + );
            right++;
        }
         len;
    }
};