滑动窗口算法思路
关于双指针的方法，可能大家并不陌生，而滑动窗口算法，其实算是双指针的一种实现方式，主要用于解决子串问题。并且在leetCode上起码有10道以上的滑动窗口应用题目，难度均在middle和hard。因此，我本文也致力于阐述自己的想法，供大家互相学习。
首先滑动窗口算法，顾名思义，就是要维护一个窗口，然后通过不断的滑动，最终跟新答案。下面是我从“Labuladuo算法小抄”上看到的伪代码：
int left = 0, right = 0; while (right < s.size()) { // 增大窗口 window.add(s[right]); right++; while (window needs shrink) { // 缩小窗口 window.remove(s[left]); left++; } }
这个算法的复杂度是O(N),比暴力算法高效许多。基本思路也就是用左右指针去维护窗口，下面是我自己一般喜欢用的代码写法：
public void SlidingWindow(String s,String t){ Map<Character,Integer> need=new HashMap<Character,Integer>(); //最终目的子串 Map<Character,Integer> Window=new HashMap<Character,Integer>(); //目前窗口集合 char [] tCharArray=t.toCharArray();
char [] sCharArray=s.toCharArray(); for(char c : sCharArray) need.put(c, need.getOrDefault(c, 0) + 1);
int left=0,right=0; int valid=0; while(right<s.length()) { char c=s.charAt(right); //c是将要移入窗口的字符 right++; //右移窗口 .... //对窗口中的数据进行更新 System.out.println("left为："+left+" right为："+right); while (window needs shrink)//判断左侧窗口是否要收缩 { char d=s.charAt(left); //d是将移出的窗口的字符 left++; //左移窗口 .... //进行窗口中数据系列更新 } }
看一道LeetCode上的hard题。
这道题暴力只是理论上可以解决的，但是，一定会超时。比如下面的写法：
for (int i = 0; i < s.size(); i++) for (int j = i + 1; j < s.size(); j++) if s[i:j] 包含 t 的所有字母: 更新答案
而通过滑动窗口算法，即可大大降低复杂度和运算时间：
public String minWindow(String s, String t) { Map<Character,Integer> need=new HashMap<>(); //子串窗口 Map<Character,Integer> window=new HashMap<>(); //滑动窗口 char [] sCharArrays=s.toCharArray(); char [] tCharArrays=t.toCharArray(); for(char c:tCharArrays){ need.put(c,need.getOrDefault(c,0)+1); //用hashmap记录出现字母的次数 } int left=0,right=0; int valid=0; int length=Integer.MAX_VALUE; int start=0; while(right<s.length()) //右指针滑动 { char c=sCharArrays[right]; //right划过窗口的元素 right++; if(need.containsKey(c)) //如果是是子串的组成字母之一，加入滑动窗口 { window.put(c,window.getOrDefault(c,0)+1); if(window.get(c).equals(need.get(c))) //如果该字母数目在滑动窗口和子串窗口中相同，valid++ valid++; } while(valid==need.size()) //当所有的字母在window和need中出现次数相同，开始收缩窗口 { if(right-left<length) { length=right-left; start=left; } char d=sCharArrays[left]; //left划出的元素 left++; if(need.containsKey(d)){ if(window.get(d).equals(need.get(d))) //注意：在这里只能写.equals(),不能写== valid--; // 因为这里是Integer对象之间的比价，如果超过 window.put(d,window.get(d)-1); //-128-127会重新new一个对象使==报错。（上面的equals同） } } } if(length==Integer.MAX_VALUE) return ""; return s.substring(start,start+length); }
最后，滑动窗口算是双指针里比较复杂的一种情况，但如果掌握大概思路，许多子串问题都能顺利的解决。
