经典滑动窗口(leetcode209)
题干
题目难度：简单
题目分析
要求找到符合大于等于target的长度最小的子数组的常规思路便是暴力破解——遍历数组，通过两层遍历，找到最小的子数组并返回。
但显而易见，这样时间复杂度会是O(n2)级别的，我们追求更好的时间复杂度，因此要考虑其他的方法。
由此，我们引入双指针法，感兴趣的小伙伴可以看我之前的运用到两个指针的leetcode学习讲解文章：
算法之二分查找优化
既然我们以左指针为遍历的时候，会出现同一个元素被多次遍历，从而造成O(n2)的时间复杂度。
那么我们以右指针为遍历的时候会怎样呢？
首先，右指针只会从头到尾遍历一遍，时间复杂度是O（n）级别的，左指针只会后移不会前移，动态地配合右指针寻找符合条件的最小子数组，因此左指针的时间复杂度也是O（n）。
从而，使整个算法达到O（n）级别的时间复杂度。
代码分析
根据上面的分析，我们需要将右指针作为遍历的指针。
每次右指针所指向的元素，加入到sum里，直到sum达到目标值target后，左指针才开始移动，将sum的值去除左指针指向的值，不断缩小左右指针之间的距离。
当sum的值小于target后退出循环，right继续右移动一位。
根据这个思路我们编写代码如下：
class Solution {public int minSubArrayLen(int target, int[] nums) {int sum=0;int left=0;int right=0;int min=nums.length+1;for(;right<nums.length;right++){sum=sum+nums[right];while(sum>=target){min=Math.min(min,right-left+1);sum=sum-nums[left];left++;}}return min==nums.length+1? 0:min;}
}
虽然这个代码套了两层的括号，但它的时间复杂度是O（n）而不是O(n2)
这是因为虽然它有两层括号，但时间上只是左右指针分别循环了一次，时间复杂度是两个O（n），每个元素分别被左右指针滑过，并不是嵌套的。
滑动窗口相关题目：leetcode904：水果成篮
题干
题目难度：中等
题目分析
上面的经典滑动窗口题目，我们已经成功完成。
上一道题的思想，是根据不同的条件判断缩小滑动窗口，我们要确保滑动窗口内的元素是连续的，右指针用来遍历，而左指针在条件触发时缩小。
同样地，这个思路可以运用到本题，针对这个题目，我们要判断出什么情况下要缩小窗口。
已知我们有两个篮子，也就意味着我们能够存储两种类型的值，比如如下的数组：
fruits = [1,2,3,2,2]
当right指针滑动到3的时候，我们发现，3已经是新的水果了，这个时候篮子无法再存储它，因此我们需要缩小窗口，将原本的左篮子存储的1值都扔掉,left指针右移，移动到2处。
这个时候，篮子存储的两种不同的值，是2和3。
比如下面的数组：
fruits = [3,3,3,1,1,1,2,3,3,4]
333111都是相同的，因此right指针在这些下标移动的时候，left指针无需移动，只需要将值加入到存储里面即可。
当right移动到2的时候，这是一个新的值，因此left指针移动，窗口要缩小，一直缩小到第一个1所在的位置。
到此为止，题目的大致思路我们便搞清楚了。
但这时候又出现了新的问题，我们应当在什么时候更新总水果数？
首先我们要搞清楚，总水果数记录的是什么，它记录的是两种不同水果的数量和，并且要求我们最终返回一个最大的值。
那么针对同一种水果，a 和 b，他们的最大和加入为max，这时候right滑动到水果c的时候，水果变成了b和c，这个时候，存储的两种水果发生了变化。
因此我们要在这个时刻更新max值，也就是存储的水果发生变化的时候。
由此，我们要在right指针循环的循环体的末尾，存储一次max值，也就是说right每移动一次，我们就更新一次max值。
- 若right指向的是原本的
ab水果，那么max值相当于是增大了1位 - 若right指向的是新水果
c，则max值相当于新的b和c水果的总和
代码编写
根据上面的分析，我们开始代码的编写。
由于用到了滑动窗口，因此我们需要两个指针left和right，分别指向窗口的左右边界。
我们需要存储两种不同的水果，以及他们的数量。
最简单的方法是创建变量，比如a,b来记录fruits[i]的值，即水果种类
sum1,sum2分别记录他们的数量。
但我们有更加方便和合适的方法——那就是Java里的map集合，HashMap
HashMap<key ,value>可以通过键值对来存储，键是唯一的，刚好可以用来存储水果，而值value则用来存储水果的数量。
当right指针移动时，我们将当前的fruits[right]作为key存储HashMap。
如果是同样的key，value+1。不同的key，则存储一个新的键值对。
当HashMap的size大于2，即有第三个水果出现的时候，left移动，我们让left指针右移，同时将它存储的值都清空。
根据以上思路，我们编写代码如下：
import java.util.HashMap;class Solution {public int totalFruit(int[] fruits) {// 使用哈希表记录每种水果的数量HashMap<Integer, Integer> fruitCount = new HashMap<>();int left = 0, max = 0;for (int right = 0; right < fruits.length; right++) {// 将当前水果加入窗口fruitCount.put(fruits[right], fruitCount.getOrDefault(fruits[right], 0) + 1);// 如果窗口内水果种类超过两种，收缩左边界while (fruitCount.size() > 2) {fruitCount.put(fruits[left], fruitCount.get(fruits[left]) - 1);if (fruitCount.get(fruits[left]) == 0) {fruitCount.remove(fruits[left]);}left++;}// 更新最大值max = Math.max(max, right - left + 1);}return max;}
}
注意fruitCount.put(fruits[right], fruitCount.getOrDefault(fruits[right], 0) + 1);这样写是简便的写法，它相当于下面的代码：
if (fruitCount.containsKey(fruits[right])) {fruitCount.put(fruits[right], fruitCount.get(fruits[right]) + 1);
} else {fruitCount.put(fruits[right], 1);
}
