904. 水果成篮
904. 水果成篮
分析
说白了，很简单，就是输出，仅包含两个不同数值的最大子数组的长度，这个其实跟 209. 长度最小的子数组 的逻辑是一样的，
209. 长度最小的子数组 中，快慢指针的移动条件是：
- 如果子数组的元素和小于指定值，就移动快指针，
- 如果子数组的元素和大于等于指定值，就移动慢指针，并更新子数组长度。
因此类比到此题中，快慢指针的移动条件是： - 快指针：在快指针的元素加入后依然满足仅包含两个不同数值的时候移动快指针，并更新子数组长度最大值，
- 慢指针：在快指针的元素加入后不满足仅包含两个不同数值的，移动慢指针，减少子数组的长度。
不过不变的是，移动快指针是增加子数组长度，移动慢指针是减少子数组长度，
然后在实际编码的时候还有一个优化的小技巧，就是我们不需要记录篮子里的水果，而是直接记录篮子里的水果在 fruits 数组中的最大索引，这样在移动慢指针的时候，只用比较索引大小即可判断我们是不是把此种类型的所有的水果都移出了篮子，即是不是该空出水果篮子了，而不用记录篮子里的水果的数量，而且记录了篮子里的水果的索引，实际上也就是记录了篮子里的水果的类型，也就是说，我们要记录篮子里有什么水果，只记录水果的索引即可。
其实，还有一个最简单的最容易想到的方案，就是官方题解提到的方案，直接用 HashMap 来当作水果篮子，上面提到的这两种方案，我们在面试那种紧张的环境下很难想到不说，在 20 分钟内也很难写对，参数太多了，用 HashMap 作为水果篮子的这种写法，基本上只要思路对了基本都能写对。
解题
这个题我花的时间有点久，其实问题不在于分析思路，思路其实就是如何解题（双指针/移动窗口）具体一点就是什么时候移动快慢指针，花的时间久主要在于细节太多了，比如如何保存篮子里的水果，移动慢指针的时候，什么时候才能把篮子空出来（需要计数）。那就用两个数组，一个数组保存种类，一个数组保存个数。
首先要定位 slow 和 fast 两个指针的定义是什么，然后按照这个定义来初始化条件，先根据 fast 计算长度，再 +1，并判断长度。
要填充两个篮子，我的思路是默认空出来第二个篮子，然后是记录这两种数字出现的次数，然后在移动满指针的时候把篮子空出来，并在需要移动的时候移动。
public int totalFruit(int[] fruits) {
if(fruits.length<=2){
return fruits.length;
}
int nowLength = -1;
// 用一个数组表示篮子里的水果的种类
int[] packages = new int[2];
packages[0]=fruits[0];
// 还没放水果就设置为-1
// 不能设置为null，只能给个-1 表示，fruits的元素都是>0的,不会冲突
packages[1]=-1;
// 再用一个数组表示篮子里的水果的数量，根据索引跟水果种类数组对应
int[] fruitCount = new int[2];
fruitCount[0]=1;
// 还没放水果就0
fruitCount[1]=0;
// slow 指的是，采摘的第一棵树
// fast 指的是准备采摘的下一个树
int slow=0,fast = 1;
for(;;){
if(fruits[fast]== packages[0] || fruits[fast]== packages[1]){
// 要摘的水果篮子里已经有了，直接放进去
//更新长度
int length = fast-slow+1;
if(length > nowLength){
nowLength = length;
}
//记录篮子里的水果的个数
if(fruits[fast]== packages[0] ){
fruitCount[0]+=1;
}
if(fruits[fast]== packages[1] ){
fruitCount[1]+=1;
}
fast++;;
if(fast>fruits.length-1){
break;
}
}else if(packages[1] == -1){
// 要摘的水果篮子里没有，那有没有空蓝子，
// 为了方便，我们只检查下标为1的位置，后面移动慢指针得时候，我们也会把下标为1的篮子空出来
packages[1]=fruits[fast];
//记录篮子里的水果的个数
fruitCount[1]=1;
//更新长度
int length = fast-slow+1;
if(length > nowLength){
nowLength = length;
}
fast++;
if(fast>fruits.length-1){
break;
}
}else{
// 要摘的水果篮子里没有，而且没有空蓝子，那就只能把篮子里的水果往外拿了
if(fruits[slow]== packages[0] ){
// 如果是第1个篮子里的水果，那就减少第1个篮子的水果的个数
fruitCount[0]-=1;
if(fruitCount[0]==0){
// 如果水果个数为0了，那就把篮子清空，同时把第2个篮子的数据移动到第1个篮子，方便后续判断。
packages[0]=packages[1];
packages[1]=-1;
fruitCount[0]=fruitCount[1];
fruitCount[1]=0;
}
}
if(fruits[slow]== packages[1] ){
// 如果是第2个篮子里的水果，那就减少第2个篮子的水果的个数
fruitCount[1]-=1;
if(fruitCount[1]==0){
// 如果水果个数为0了，那就把篮子清空，
packages[1]=-1;
}
}
slow++;
}
}
return nowLength;
}
同时，我们还有优化的空间，就是我们有没有必要保存篮子里的水果的个数，在移动慢指针的时候，水果的个数需要加减，很麻烦，我们可以记录篮子里的水果的最大索引，这样只用比较索引大小即可判断是不是已经把此种类型的所有水果都移出了篮子，比较方便。然后我就发现，我都记录了水果的索引了，那也就没有必要记录水果 packages 数组了，有了索引，直接通过水果数组加上索引 fruits[index] 来访问即可，所以又可以节约代码了。
public int totalFruit(int[] fruits) {
if(fruits.length<=2){
return fruits.length;
}
int nowLength = -1;
int slow=0,fast=1;
int[] packageIndex = new int[]{0,-1};
for(;fast<fruits.length;){
// 通过最大索引判断篮子里是否已经有水果
// 如果没有水果，或者有水果，就是fast指向的这个水果，那就可以直接放入，同时更新水果的最大索引
if(packageIndex[0]==-1||fruits[fast]==fruits[packageIndex[0]]){
packageIndex[0] = fast;
int length = fast-slow+1;
if(nowLength < length){
nowLength = length;
}
fast++;
}else if(packageIndex[1]==-1||fruits[fast]==fruits[packageIndex[1]]){
packageIndex[1] = fast;
int length = fast-slow+1;
if(nowLength < length){
nowLength = length;
}
fast++;
} else {
// 如果两个篮子里都不能放，则开始收缩
// 只需要比较最大索引就可以直接判定是否清空篮子
if(slow==packageIndex[0]){
packageIndex[0]=-1;
}
if(slow==packageIndex[1]){
packageIndex[1]=-1;
}
slow++;
}
}
return nowLength;
}
官方题解倒是简单，直接用一个 HashMap 来表示水果篮子，key 就是水果品种，value 就是水果的个数，这其实是在面试中的推荐方案，上面提到的这两种方案，我们在面试那种紧张的环境下很难想到不说，在 20 分钟内也很难写对，参数太多了，用 HashMap 作为水果篮子的这种写法，基本上只要思路对了基本都能写对。
public int totalFruit(int[] fruits) {
if(fruits.length<=2){
return fruits.length;
}
// 找到只包含两种元素的最长子数组的长度
int minValue=0;
int maxArrayLength = minValue;
// 我们对left和right的定义就是 [left,right]确定子数组的范围。
int left=0,right=0;
//[0,0]表示已经有一个元素在子数组中了
int subArrayLength=1;
Map<Integer,Integer> basket = new HashMap<>();
// 篮子中已经有一个水果了
basket.put(fruits[0],1);
while(true){
if((right+1)>=fruits.length){
break;
}
// 两个篮子中还有空的，或者接下来的水果的类型跟篮子里的水果的类型相同，则移动右指针
if(basket.keySet().size()<2 || basket.containsKey(fruits[right+1])){
int num = basket.getOrDefault(fruits[right+1],0);
basket.put(fruits[right+1],num+1);
right++;
int newLength = right-left+1;
if(newLength>maxArrayLength){
maxArrayLength = newLength;
}
}else{
// 遇到类型不一样的水果，移动左指针
int typeVal = fruits[left];
int num = basket.get(typeVal);
if(num-1==0){
// 个数为0，可以清空篮子了
basket.remove(typeVal);
}else{
basket.put(typeVal,num-1);
}
left++;
}
}
return maxArrayLength;
}
相关题
26. 删除有序数组中的重复项
27. 移除元素
283. 移动零
844. 比较含退格的字符串
977. 有序数组的平方
滑动窗口
209. 长度最小的子数组
76. 最小覆盖子串