https://blog.csdn.net/2601_95366422/article/details/158584220
上节课的链接
一.题目
904. 水果成篮 – 力扣（LeetCode）
二.思路讲解
2.1 审题
这道题描述的场景虽然文字较多，但核心要点其实很清晰：
-
你有两个篮子，每个篮子只能装同一类水果（但可以装无限个）。
-
你从一排果树前走过，每遇到一棵树就必须摘它的水果，并且只能放入其中一个篮子。
-
如果遇到一棵树的水果类型，两个篮子里都没有，那么你就必须停止。
换句话说，问题转化为：在给定的水果序列中，找到一个最长的连续子数组，使得其中包含的水果种类不超过两种。这就是经典的“最多两种不同字符的最长子串”问题，可以用滑动窗口高效解决。
2.2 思路解决
既然要用滑动窗口，我们就需要解决两个关键点：如何维护窗口内不同水果的种类数，以及如何高效地判断和更新。最直接的想法是用哈希表记录每种水果出现的次数，但考虑到题目中水果类型的范围是 1 到 100000，我们可以用一个固定大小的数组来模拟哈希表，这样既简单又高效。数组的下标对应水果类型，值记录该水果在窗口内出现的次数。
接下来就是滑动窗口的标准操作：
-
进窗口：每次右指针向右移动，将当前水果加入窗口，对应的计数加1。
-
判断条件：如果窗口内不同水果的种类数超过了2，就需要出窗口，即移动左指针，将左边的水果移出窗口，同时将其计数减1；若某个水果的计数减到0，则种类数减少。
-
更新结果：在每次调整后，当窗口内种类数不超过2时，记录当前窗口的长度，并更新最大值。
三.代码演示
class Solution {
public:
int totalFruit(vector<int>& fruits)
{
int nums[100001] = {0};//数组，去重的
int basket = 0;//篮子计数器
int n = fruits.size();
int len = 0;
for(int left = 0,right = 0;right < n;right++)
{
nums[fruits[right]]++;//进窗口
//篮子被用了
if(nums[fruits[right]] == 1)
basket++;
//判断条件
while(left < right && basket > 2)
{
nums[fruits[left]]–;
if(nums[fruits[left]] == 0)
basket–;
left++;
}
len = max(len,right – left + 1);
}
return len;
}
};
四.代码讲解
第一步：初始化辅助数组和变量 定义一个大小为 100001 的整型数组 nums，并将所有元素初始化为 0。这个数组用于记录每种水果在当前窗口中出现的次数，因为题目给出的水果类型范围是 1 到 100000，所以数组大小足够。 定义变量 basket 用于统计当前窗口中不同水果的种类数，初始值为 0。 获取数组长度 n = fruits.size()，定义变量 len 用于存储最长连续子数组的长度，初始值为 0。同时初始化左指针 left = 0 和右指针 right = 0。
第二步：遍历数组，移动右指针（进窗口） 使用 for 循环，让右指针 right 从 0 到 n-1 依次遍历。每次循环执行以下操作：
-
将当前右指针指向的水果 fruits[right] 在数组 nums 中的计数加 1，即 nums[fruits[right]]++，表示该水果进入窗口。
-
如果该水果的计数在加 1 后等于 1（即之前窗口中没有这种水果），则将 basket 加 1，表示新增加了一种水果种类。
第三步：判断窗口内水果种类是否超过 2 如果当前 basket > 2，说明窗口中包含了三种或以上的不同水果，需要收缩左边界（出窗口）来减少种类数。 在 while (left < right && basket > 2) 循环中执行以下操作：
-
将左指针指向的水果 fruits[left] 在数组 nums 中的计数减 1，即 nums[fruits[left]]–，表示该水果移出窗口。
-
如果该水果的计数在减 1 后等于 0，说明窗口中已经没有这种水果了，则将 basket 减 1，表示种类数减少。
-
将左指针 left 向右移动一位（left++），继续检查是否仍超过 2 种。
第四步：更新最长长度 当窗口内水果种类不超过 2 时（即退出 while 循环后），计算当前窗口的长度 right – left + 1，并用它更新 len，取较大值：len = max(len, right – left + 1)。这一步记录下当前满足条件的最长窗口长度。
第五步：返回结果 遍历结束后，len 中存储的就是可以摘到的最大水果数量（即最长连续子数组的长度），将其返回。
重点总结
-
核心数据结构：一个固定大小的数组 nums 充当哈希表，高效记录每种水果的出现次数。
-
关键变量 basket 实时统计窗口内不同水果的种类数。
-
滑动窗口的四个动作：进窗口（右移并更新计数和种类）、判断条件（种类是否超过 2）、出窗口（左移并更新计数和种类）、更新结果（记录当前最长长度）。
-
整个过程只遍历数组一次，时间复杂度 O(n)，空间复杂度 O(1)（因为数组大小固定）。
