水果成篮 ---- 滑动窗口

本文主要是介绍水果成篮 ---- 滑动窗口，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 题目链接

题目：

 

分析：

• 题目中， 我们只能连续采摘树， 而且采摘的树不能超过两种，找到可以包含最多树的方案， 所以我们可以理解为： 找到最长的连续子数组， 子数组中的数据种类不大于两种， 因为是找连续子数组， 我们很容易可以想到要用“滑动窗口”
• 我们需要记录子数组的数据种类及出现的次数， 所以可以使用map容器
• 定义left = 0，right = 0
• 进窗口  让right指针进窗口，存在key， 更新value的值
• 判断  如果子数组的数据种类大于2，即map的size大于2
• 出窗口  让left指针出窗口， 并更新value的值， 如果此时value值为0，则删除对应的key
• 更新结果 记录最大的长度， 并返回

代码： 

class Solution {public int totalFruit(int[] fruits) {Map<Integer,Integer> hash = new HashMap<>();int left = 0;int right = 0;int ret = 0;while(right<fruits.length){hash.put(fruits[right],hash.getOrDefault(fruits[right],0)+1);while(hash.size() > 2){hash.put(fruits[left],hash.get(fruits[left])-1);if(hash.get(fruits[left]) == 0){hash.remove(fruits[left]);}left++;}ret = Math.max(ret,right-left+1);right++;}return ret;}
}

用map容器， 当我们提交代码时， 发现时空代价较大，所以我们可以使用hash数组， 记录fruits数组中数据对应hash表的下标， 用hash表记录出现的次数， 需要额外定义一个变量记录此时的类型数量 

class Solution {public int totalFruit(int[] fruits) {int[] hash = new int[fruits.length];int left = 0;int right = 0;int size = 0;int ret = 0;while(right<fruits.length){if(hash[fruits[right]] == 0){size++;}hash[fruits[right]]++;while(size > 2){hash[fruits[left]]--;if(hash[fruits[left]] == 0){size--;}left++;}ret = Math.max(ret,right-left+1);right++;}return ret;}
}

这篇关于水果成篮 ---- 滑动窗口的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---