题目大意：
最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。 - 如果 S 中存在这样的子串，我们保证它是唯一的答案。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=76
解题思路分析：
这是一道经典的双指针题目。我们需要在字符串S中找到一个子区间，该区间内要包含字符串T的所有字符，举个例子，如果T中有1个a，3个b，那么该S的子区间内也要包含至少1个a和3个b，另外该区间内也可以包含其他无关字符。
解题时，我们需要先遍历一遍字符串T，统计出它包含每种字符的个数。然后开始利用双指针方式遍历字符串S。初始时，左指针与右指针均处于S下标为0的位置。我们开始向右移动右指针，查看右指针所指的字符是否在T中出现过，若没出现过，继续向右移动。反之如果出现过，还需要看该字符在S中出现过的次数，如果该次数小于等于T中出现的次数，说明我们找到了一个合理的字符，此时更新一下找到的合理字符数（加一）。
当合理字符数等于字符串T的长度时，说明当前子区间（左指针到右指针范围）内包含了T的全部字符，当前区间为一个合理区间，并更新一下全局最短合理区间长度。此时开始尝试向右移动左指针，左指针划过的位置代表该字符被移除出区间范围，如果该字符存在于字符串T中，并且移除该字符后，当前区间内该字符数量小于了T中该字符的数量，说明这时区间内并不能包含所有T中的元素，合理字符数应减一，并结束移动左指针，返回继续移动右指针。反之继续移动左指针。
实现代码：
public String minWindow(String s, String t) {
// t中每种字符的个数
int[] count = new int[58];
// 字符串S的长度
int lengthS = s.length();
// 字符串T的长度
int lengthT = t.length();
// 统计字符串T中每种字符的个数
for(int i=0;i<lengthT;i++){
count[t.charAt(i)-'A']++;
}
// 左指针，右指针
int left=0, right=0;
// 最小区间长度
int minLength=Integer.MAX_VALUE;
// 返回结果
String res="";
// 区间内总合理字符个数
int countAll=0;
// 区间内每种字符出现的个数
int[] count2 = new int[58];
while(right<lengthS){
// 右指针指向的字符
int c = s.charAt(right)-'A';
// 如果该字符在T中出现过
if(count[c]>0){
// 更新区间内该字符数量（加一）
// 如果该数量小于等于T中出现的数量，
// 合理字符数加一
if(++count2[c]<=count[c]) countAll++;
}
// 如果合理字符数等于T的长度，此时为合理区间
while(countAll==lengthT){
// 如果该区间长度小于全局最小长度
if(right-left+1<minLength){
// 更新当前长度为最小长度
minLength = right-left+1;
// 当前区间子串为返回结果
res=s.substring(left, right+1);
}
// 左指针指向的字符
int cl=s.charAt(left)-'A';
// 如果该字符在T中出现过
if(count[cl]>0){
// 将该字符从区间内移除，该字符区间内出现次数减一
// 该字符区间内出现次数小于T中出现次数，区间内合理字符数量减一
if(--count2[cl]<count[cl]) countAll--;
}
left++; // 移动左指针
}
right++; // 移动右指针
}
return res;
}本题解法执行时间为4ms。
Runtime: 4 ms, faster than 80.45% of Java online submissions for Minimum Window Substring.
Memory Usage: 38.5 MB, less than 89.36% of Java online submissions for Minimum Window Substring.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-76-minimum-window-substring-解题思路分析/