Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
題意：在字符串S中找到包含所有字符串T中字符的最短子串癣蟋，如果找不到返回空字符串恢共。T中可能存在重復(fù)字符，如aac，此時(shí)S中的最短子串中必須也要有兩個(gè)a。
自己的思路是用一個(gè)整型數(shù)組作為map存T中包含的字符，遍歷S，用一個(gè)隊(duì)列存遍歷過的字符，如果字符在map中并且值大于0带欢，就將這個(gè)值減一，當(dāng)這個(gè)map中所有值都是0的時(shí)候烤惊，就找到了一個(gè)包含T的子串乔煞。考慮后覺得每次都check一次map撕氧，效率很低瘤缩，想到可以用一個(gè)count計(jì)數(shù)來判斷。但是這個(gè)做法有個(gè)問題伦泥，就是無法縮短隊(duì)列剥啤，更新最短長度。
最后查看discuss的解法后發(fā)現(xiàn)：
1不脯、用map的思路是一樣的府怯。但是正解沒有用隊(duì)列來存儲字符串，而是通過兩個(gè)指針來表示防楷；
2牺丙、不是只更新map中T含有的字符的值，而是對所有遍歷到的S的字符，都對map做--操作冲簿。這樣在更新左指針的時(shí)候粟判，只要相應(yīng)的++就可以了驻襟。
public String minWindow(String s, String t) {
if (s == null || s.length() == 0) {
return "";
}
int[] map = new int[256];
for (int i = 0; i < t.length(); i++) {
map[t.charAt(i)]++;
}
int count = t.length(), head = 0, begin = 0, end = 0, min = Integer.MAX_VALUE;
while (end < s.length()) {
if (map[s.charAt(end)] > 0) {
count--;
}
map[s.charAt(end)]--;
while (count == 0) {
if (end - begin + 1 < min) {
min = end - begin + 1;
head = begin;
}
if (map[s.charAt(begin)] == 0) {
count++;
}
map[s.charAt(begin)]++;
begin++;
}
end++;
}
return min > s.length() ? "" : s.substring(head, head + min);
}