这里总结一下这一类题目
主要就是给你一个字符串，然后需要你找到最怎么怎么样的子串，其中这些子串满足某些条件，基本的解决思路就是使用一个hashMap和两个指针，两个指针在要求的条件控制下移动。当然了，如果都是可表示字符的话，可以使用一个128的数组来替代这个hashMap。
下面我们具体来看几个例子：
题目一：给你一个字符串s和t，要求找到s的一个最小子串，其中这个子串满足包含t中的所有字符。
[leetcode76]https://leetcode.com/problems/minimum-window-substring/
算法步骤&原理
使用一个128的数组来记录每个字符出现的次数
- 首先遍历一遍t,map中记录了每个字符出现的次数
- 遍历字符串s,使用left和right作为左右边界。如果当前字符在map中大于0,证明是一个“有效字符”,count++。当count==tLen的时候表明找到了一个满足条件的窗口，更新全局记录的最小窗口，然后这时候应该移动left,直到移走一个“有效字符”
代码
public class Solution {
public String minWindow(String s, String t) {
if(s==null||s.length()==0||t==null||t.length()==0)
return "";
int[] map=new int[128];
char[] tChars=t.toCharArray();
char[] sChars=s.toCharArray();
for(char c:tChars){
map[c]++;
}
int left=0;
int right=0;
int minBegin=0;
int winLen=Integer.MAX_VALUE;
int tLen=t.length();
int sLen=s.length();
int count=tLen;
while(right<sLen){
if(map[sChars[right]]>0)
count--;
map[sChars[right]]--;
right++;
while(count==0){
if(right-left<winLen){
winLen=right-left;
minBegin=left;
}
if(++map[sChars[left]]>0)
count++;
left++;
}
}
return winLen==Integer.MAX_VALUE?"":s.substring(minBegin,minBegin+winLen);
}
}
延伸
比如求解最多包含两个不同字符的最长子串
比如求解没有重复字符的最长子串，都可以使用这个算法原型。
