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

13 水果成篮

题目描述

题目示例

解法思路（滑动窗口）

这道题的核心在于处理一段连续的区间，非常适合用滑动窗口的思路来拆解。

我们需要让滑动窗口满足一个条件：窗口内包含的水果种类不能超过两种。具体操作上，每当右指针指向的水果加入窗口，我们就用哈希表记录它的出现次数。进来后立刻检查哈希表的大小：

• 如果大小超过 2，说明当前窗口里水果种类超标了。这时候得从最左侧开始依次移除水果，直到哈希表里的种类数降回 2 以内，同时更新最大长度结果；
• 如果没超过 2，说明当前窗口合法，直接更新一下结果长度即可。

算法流程

1. 初始化一个哈希表 hash，用来统计窗口内每种水果的数量。
2. 设置左右指针 left = 0, right = 0，以及记录结果的变量 len = 0。
3. 当 right 小于数组大小时，循环执行以下逻辑：
   • 将当前水果放入哈希表计数。
   • 检查哈希表大小是否超过 2：
     • 若超过，则不断将左侧元素滑出窗口，并在哈希表中将该元素的频次减一；
     • 如果某个元素的频次减到 0，直接从哈希表中删除该键；
     • 重复上述过程，直到哈希表中的大小不超过 2。
   • 更新结果 len 为当前窗口长度与历史最大值中的较大者。
   • right++，继续向右扩展。
4. 循环结束后，len 即为最终答案。

C++ 代码演示：方法一（使用容器）

这里用的是标准库的 unordered_map，如果你刚接触哈希表，这个版本更容易理解。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 使用 unordered_map 统计窗口内水果的种类和数量
        unordered_map<int, int> hash;
        int left = 0;
        int right = 0;
         len = ;
        
         (right = ; right < fruits.(); right++) {
            hash[fruits[right]]++; 
            
            
             (hash.() > ) {
                hash[fruits[left]]--; 
                 (hash[fruits[left]] == ) {
                    hash.(fruits[left]); 
                }
                left++; 
            }
            
            
            len = (len, right - left + );
        }
         len;
    }
};