遇到子串问题，首先想到的就是滑动窗口技巧
总结出滑动窗口算法的抽象思想：
int left = 0, right = 0;
while (right < s.size()) {
window.add(s[right]);
right++;
while (valid) {
window.remove(s[left]);
left++;
}
}滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
两种思路，一种用 set(前两块代码) ,一种用map（最后一块）
public int lengthOfLongestSubstring(String s){
// 定义返回的最大长度,左右指针
int Max=0,left=0,right=0;
char[] charArray=s.toCharArray();
// Set 去重
Set<Character> set=new HashSet<>();
for (int i = 0; i < s.length(); i++) {
// 如果当前字母加入窗口中会造成重复,则不断移动左指针直到没有重复字母为止
while (set.contains(charArray[i])) set.remove(charArray[left++]);
// 当不会造成重复时加入
set.add(charArray[i]);
int temp=right-left+1;
right++;//right 指针右移
// 尝试更新最大值
Max=temp>Max?temp:Max;
}
return Max;
}//使用 window 作为计数器记录窗口中的字符出现次数，然后先向右移动 right，当 window 中出现重复字符时，开始移动 left 缩小窗口，如此往复
class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0,left = 0,right = 0;
Set set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
while (set.contains(s.charAt(i))) {
//缩小窗口，调整左指针
//如果当前字母加入窗口中会造成重复,则不断移动左指针直到没有重复字母为止
set.remove(s.charAt(left));
left++;
}
//当不会造成重复时加入
set.add(s.charAt(i));
max = Math.max(max, i - left + 1);
}
return max ;
} public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int maxLen = 0;//用于记录最大不重复子串的长度
int left = 0;//滑动窗口左指针
for (int i = 0; i < s.length() ; i++)
{
1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；
2、如果当前字符 ch 包含在 map中，此时有2类情况：
1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
应该不变，left始终为2，子段变成 ba才对。
为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
if(map.containsKey(s.charAt(i)))
{
left = Math.max(left , map.get(s.charAt(i))+1);
}
//不管是否更新left，都要更新 s.charAt(i) 的位置！
map.put(s.charAt(i) , i);
maxLen = Math.max(maxLen , i-left+1);
}
return maxLen;
}class Solution {
// 滑动窗口
public String minWindow(String s, String t) {
Map<Character,Integer> window = new HashMap(); // 存储当前窗口中字符及其个数
Map<Character,Integer> need = new HashMap(); // 存储字符串t中字符及其个数
for(char c : t.toCharArray()) need.put(c,need.getOrDefault(c,0)+1); // 存放字符串t
int left = 0, right = 0; // 窗口左右指针(左闭右开)
int start = 0, len = Integer.MAX_VALUE; // 存储最终结果的起始下标与长度.
int valid = 0; // 表示window中包含need中字符的个数
while(right < s.length()){
char ch = s.charAt(right); // 当前位置字符
right++; // 由于是左闭右开[0,0)，最开始时是没有元素的，需要更新窗口
if(need.containsKey(ch)){ // 扩大窗口
window.put(ch,window.getOrDefault(ch,0)+1); // 如果字符串t包含ch，则更新窗口中的字符
// 只有window中与need同时包含该字符，则个数也相同时，才更新valid
// 使用equals判断，因为Integer是对象， == 判断的是内存地址，equals重写后判断的是内容
if(window.get(ch).equals(need.get(ch))) valid++;
}
// 判断是否收缩左窗口
while(valid == need.size()){ // 说明当前已满足s包含t，但不一定是最小的窗口
// 更新最小覆盖子串
if(right - left < len){ // 如果当前窗口的长度小于前一个窗口，则收缩窗口
start = left;
len = right - left;
}
// 窗口最左端的字符
char remove = s.charAt(left);
left++; // 开始收缩
if(need.containsKey(remove)){
// 使用equals判断，因为Integer是对象， == 判断的是内存地址，equals重写后判断的是内容
if(window.get(remove).equals(need.get(remove))){
valid--;
}
window.put(remove,window.get(remove)-1); // 此时window一定包含remove
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
}
} public static boolean checkInclusion(String s1, String s2) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (Character c : s1.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int vaild = 0;
while (right < s2.length()) {
Character c = s2.charAt(right);
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
vaild++;
}
}
while (need.size() == vaild) {
//长度一致可以返回
if (right - left + 1 == s1.length()) {
return true;
}
Character remove = s2.charAt(left);
if (need.containsKey(remove)) {
if (window.get(remove).equals(need.get(remove))) {
vaild--;
}
window.put(remove, window.getOrDefault(remove, 0) - 1);
}
//移动左指针
left++;
}
//移动右指针
right++;
}
return false;
}/**
* 因为这道题和[76.最小覆盖子串]的场景类似，也需要 window 中包含串 t 的所有字符，
但上一道题要找长度最短的子串，这道题要找长度相同的子串，也就是「字母异位词」嘛。
*/
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> window = new HashMap<>();
HashMap<Character, Integer> need = new HashMap<>();
int left = 0, right = 0;
List res = new ArrayList<>();
int vaild = 0;
//初始化 need
for (Character c : p.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
while (right < s.length()) {
Character c = s.charAt(right);
right++;
if (need.containsKey(c)) {
//扩大窗口
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
vaild++;
}
}
while (need.size() == vaild) {
//找到一个子串
if (right - left == p.length()) {
res.add(left);
}
//缩小窗口
Character remove = s.charAt(left);
if (need.containsKey(remove)) {
if (window.get(remove).equals(need.get(remove))) {
vaild--;
}
window.put(remove, window.getOrDefault(remove, 0) - 1);
}
left++;
}
}
return res;
}
}