顾名思义，滑动窗口就是滑动的窗口，在字符串上从左往右滑动，直到串尾。滑动窗口的窗口长度是动态变化的，所以用两个指针来维护，一个是指针指向窗口的右边界姑且命名为left，一个指针指向窗口的左边界姑且命名为right。
1 使用到的变量
窗口左端left
窗口右端 right
right的作用是不断增加窗口的宽度(拉伸窗口)
left是让字符串不满足要求(移动窗口)
2 案例分析
求匹配给定字符串的字符串子串的最小长度
right是让窗口满足要求,不满足的时候，right不断的向右移动（不断的拉伸窗口）。Right不断移动，知道条件满足。
具体流程如下：
窗口为’A’，不满足要求，right右移。由于包含的了一个子串字符’A‘ count++，当count=3的时候，表示这三个条件都满足了。
窗口为’AD’，不满足要求，right右移。count不变。
窗口为’ADO’，不满足要求，right右移。count不变。
窗口为’ADOB’，不满足要求，right右移。count++。
窗口为’ADOBE’，不满足要求，right右移。count不变。
窗口为’ADOBEC’，满足要求，right不要右移（窗口不要再拉动了，这时候已经满足要求了）。我们要记录下窗口的长度,ans=6。
当满足的时候，left开始发挥作用，移动窗口，使其条件不满足。寻找下一个满足条件的窗口。此时，count--。
下一个满足条件的位置,right=10.这个窗口ans比原来的ans大，所以ans不更新。
Left的作用是使得条件不符合，所以，left会跳到6.
3 实际应用
（1）求字符串的非重复的最长的子串
package StringDemo;
import java.util.HashSet;
import java.util.Set;
/**
* @author du
* 求字符串最长的非重复子串
*/
public class Demo {
public static int lengthOfLongestSubstring(String s) {
int len = s.length();
// 满足条件的窗口的长度
int ans = 0;
// 窗口左指针
int left = 0;
// 窗口右指针
int right = 0;
// 存放窗口
Set<Character> set = new HashSet<Character>();
while (left < len && right < len) {
// 如果窗口里面没有重复的值,那么right要不断的向右移动(拉伸窗口)
if (!set.contains(s.charAt(right))) {
set.add(s.charAt(right++));
ans = Math.max(ans, right - left);
} else {
// 如果窗口中有重复值了,那么left要向右移动(窗口移动),知道窗口的条件不再满足
set.remove(s.charAt(left++));
}
}
return ans;
}
public static void main(String[] args) {
int ans = lengthOfLongestSubstring("aaabbbbccc");
System.out.println(ans);
}
}
（2）求匹配字符串的字符串中的最小子串（要求字符串非重复）
package StringDemo;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
/**
* @author Du 求字符串包含某字符串的非连续的最短的子串的长度。
* 假设这两个字符串都没有重复的字符，如果有重复值那么就需要为每一个要匹配的字符设置一个count,我们就不这么麻烦了。
*/
public class Demo2 {
public static boolean isAllSatisfied(Map<Character, Integer> map) {
for (int i : map.values()) {
if (i == 0) {
return false;
}
}
return true;
}
public static int lengthOfLongestSubstring(String s, String t) {
// 保存要匹配的字符，并记录匹配的数量，不匹配为0，匹配为1
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < t.length(); i++) {
map.put(t.charAt(i), 0);
}
// 定义窗口
int left = 0;
int right = 0;
int ans = s.length();
int len = s.length();
// 是否存在匹配
boolean isExsit = false;
while (!map.keySet().contains(s.charAt(left))) {
left++;
}
while (left < len && right < len) {
// 如果匹配到了字符。先要判断是否全部匹配，如果全部匹配，那么left右移。否则，right右移。
if (map.keySet().contains(s.charAt(right))) {
// 把匹配到的字符设置为1
map.put(s.charAt(right), 1);
// 如果全部满足了
if (isAllSatisfied(map)) {
isExsit = true;
// 取一个最小的窗口
ans = Math.min(ans, (right - left) + 1);
// left右移找到下一个不满足的点
while (left < right) {
if (map.containsKey(s.charAt(left))) {
map.put(s.charAt(left++), 0);
break;
}
}
}
}
// 如果不匹配，right右移
right++;
}
if (!isExsit) {
return -1;
}
return ans;
}
public static void main(String[] args) {
int n = lengthOfLongestSubstring("abcdefg", "bdfa");
System.out.println(n);
}
}
