1、题目描述
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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
If there is no such window in S that covers all characters in T, return the empty string " ".
If there is such a window, you are guaranteed that there will always be only one unique minimum window in S.
2、问题描述：
- 两个字符串，求第二个字符串出现在第一个字符串中的最小长度。
3、问题关键：
- 双指针做法。
- 需要维护两个hash表。
-
思路：先将第2个串t的所有字符加入hash表中，并记录每个元素的个数。然后用两个指针i， j。i是前指针，j是后指针，遍历一遍s，对于每个元素先加入hash表中并记录个数，如果个数和t的相应元素个数相同那么satisfy++，如果因为加入元素使元素大于t的相应元素个数，那么指针向后移动一个，并且使元素减减，如果下一个位置元素还大于，那么继续后移(这一点也比较关键）。时间复杂度为
.
4、C++代码：
class Solution {//这是一个题经典的双指针问题。
public:
string minWindow(string s, string t) {
string res;
unordered_map<char, int> S,T;
for (auto c : t) T[c] ++;//将t放入hash表中。
int total = T.size();//这是T.size(),不是t。代表的是元素的种类。
int satisfy = 0;//判断是否保护所有的元素。
for (int i = 0, j = 0; i < s.size(); i ++) {//这是一个双指针的做法。
S[s[i]] ++;//将s中的元素加入hash表中
if (S[s[i]] == T[s[i]]) satisfy ++;//如果前面包含刚好和相同个数的特定元素，那么就satisfy++。
while(S[s[j]] > T[s[j]]) S[s[j ++]] --;//如果元素超了，那么就向后移动一格，当然那个元素也需要被剪掉一个。否则后面会删掉多，把本来不多的给删掉了。
if (satisfy == total && (res.empty() || i - j + 1 < res.size())) {//如果包含了所有的元素，若答案为空，或者当前区间更短，那么更新答案。
res = s.substr(j, i - j + 1);
}
}
return res;
}
};
