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

13 水果成篮

题目描述

示例

解法（滑动窗口）

算法思路

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

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

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

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

算法流程

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

C++ 代码演示：方法一 (使用容器)

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 方法一：使用容器 (如果对哈希掌握不是很好可以看下面方法二)
        unordered_map<int, int> hash;
        // 统计窗口内出现水果的种类
        int left = 0;
        int right = 0;
        int len = ;
        (right = ; right < fruits.(); right++) {
            hash[fruits[right]]++;
            
            (hash.() > ) 
            {
                hash[fruits[left]]--;
                
                (hash[fruits[left]] == ) {
                    hash.(fruits[left]);
                }
                left++;
            }
            len = (len, right - left + );
            
        }
         len;
    }
};