滑动窗口
1. 概念解释
是双指针的一种，有快慢两个指针，慢指针指向窗口的起始位置，快指针指向窗口的末端位置；
不断的调节子序列的起始位置和终止位置，从而得出结果。
2. 解题思路/模板
int left;//左指针
int right;//右指针
int var;//随着窗口变化的量
for(int right =0; rightd的范围;right++){
对var的操作；
//修改var的值，且伴随着left的右移
while(){
...
left++;
}
return var;
}
3. 具体例子
（1）LeetCode 209 长度最小的子数组
private static int solution(int s, int[] nums){
int sum = 0;
int left=0;
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum+=nums[right];
while (sum>=s){
result = Math.min(result,(right-left+1));
sum-=nums[left++];
}
}
return result==Integer.MAX_VALUE?0:result;
}
（2）LeetCode904 水果成篮
//自己写的第一版
public static int solution1(int[] fruits){
if(fruits==null){
return -1;
}
if(fruits.length<=1){
return fruits.length;
}
int left1=0;
int left2=-1;
int result= 1;
int temp=1;
for (int right = 1; right < fruits.length; right++) {
temp = right -left1+1;
if(left2==-1 && fruits[left1]!=fruits[right]){
left2=right;
}else{
if(fruits[right]!=fruits[left1] && fruits[right]!=fruits[left2]){
result = Math.max(temp-1,result);
left1=left2;
left2=-1;
right=left1;
}
}
}
return result>temp?result:temp;
}
//leeetcode的题解(自己加了一点点注释)，更能体现滑动窗口的思想
public static int solution2(int[] fruits){
int n = fruits.length;
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
int left = 0, ans = 0;
for (int right = 0; right < n; ++right) {
//getOrDefault()是指返回某个key的value，若不存在则返回制定的默认值
cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
//从左往右，依次进行删除，直到哈希表的长度不大于2
while (cnt.size() > 2) {
cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
if (cnt.get(fruits[left]) == 0) {
cnt.remove(fruits[left]);
}
++left;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
（3）LeetCode76 最小覆盖子串
public static String solution(String s, String t){
Map<Character,Integer> map = new HashMap();
for (int i = 0; i < t.length(); i++) {
map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0)+1);
}
int left = 0;
int[] result = {0,s.length()};
for (int right = 0; right < s.length(); right++) {
if(map.containsKey(s.charAt(right))){
map.replace(s.charAt(right),map.get(s.charAt(right))-1);
}
while(nonNegative(map)){
if((result[1]-result[0])>(right-left)){
result[0] = left;
result[1] = right;
}
if(map.get(s.charAt(left))!=null){
map.replace(s.charAt(left),map.get(s.charAt(left))+1);
}
left++;
}
}
return result[1]==s.length()?"":s.substring(result[0],result[1]+1);
}
//判断map是否有值非负的键值对，若有则返回false
private static boolean nonNegative(Map map){
Iterator<Integer> it = map.values().iterator();
while(it.hasNext()){
if(it.next()>0){
return false;
}
}
return true;
}