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

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 = 0;
        for(right = 0; right < fruits.size(); right++) {
            hash[fruits[right]]++; // 进窗口
            while(hash.size() > 2) { // 判断
                hash[fruits[left]]--; // 出窗口
                if(hash[fruits[left]] == 0) {
                    hash.erase(fruits[left]);
                }
                left++;
            }
            len = max(len, right - left + 1); // 更新结果
        }
        return len;
    }
};

C++代码演示：方法二 (用数组模拟哈希表)

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 方法二：用数组模拟哈希表 (只需要了解哈希可以对数据存放的次数进行计数即可)
        int hash[100001] = { 0 }; // 根据题目提示可知水果种类最多不超过 100000
        int left = 0;
        int right = 0;
        int len = 0;
        int kinds = 0; // 用一个新变量来维护水果种类
        for(right = 0; right < fruits.size(); right++) {
            if(hash[fruits[right]] == 0) {
                kinds++;
            }
            hash[fruits[right]]++; // 进窗口
            while(kinds > 2) { // 判断
                hash[fruits[left]]--; // 出窗口
                if(hash[fruits[left]] == 0) {
                    kinds--;
                }
                left++;
            }
            len = max(len, right - left + 1); // 更新结果
        }
        return len;
    }
};

算法总结及流程解析：