思路分析
又是一道很有意思的字符串处理问题，原理基于经典的滑动窗口思路。我们从起始位置开始，首先滑动窗口的右端，直至包含了T串中的所有字符（需要考虑重复）。此时，当前窗口并非局部最优，因为我们最好滑动窗口的左端，把不属于T的那些字符，以及尽管属于T但是没有的话同样合法的字符（即多出来的）排除出去。这样，我们得到了第一个合法的窗口。
算法线性复杂度的核心，就在于如何使用O(1)的时间，来获得下一个合法的窗口。考虑当前的窗口，左右两端均已最优，这样我们可以放弃左端的一个字符（肯定是属于T并且必须包含在窗口中的），让右端继续滑动，则一定能够抵达下一个紧邻的合法的窗口。这样一直遍历下去，记录长度最小的答案即可。
Update: 微软的在线面试过程中就撞见了这道题。
Update2: 这题大公司面试好像非常常见，套路跟leetcode 438是一模一样的，都是利用滑动窗口求某个最短子序列的问题。这类题有个非常明显的技巧，就是我维护一个额外变量cnt，来记录当前的窗口中有多少个我期望看到的字符，头部往前移动的时候可能会增加这个值，尾部往前移动的时候可能会减小这个值。那么如何判定这个字符是我期望的呢？我们要在滑动过程中对哈希表里面的值进行加加减减：如果我减掉以后大于等于零，说明我希望看到这个字符，cnt++；如果尾部往前移动时把哈希表条目增加以后大于零，说明这个字符是我所期望的，但它已经不在集合里面了，于是cnt--。
另外记住，滑动窗口题目，如果要求最小窗口之类的，一定是先if判断能否移动头部，然后while缩短尾部。
代码
Find All Anagrams in a String
:::C++
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if (s.empty()) return {};
vector<int> res;
int pat[256] = {0};
for (auto c: p) { pat[c]++; }
int head = 0, tail = 0, cnt = p.size();
while (head < s.size()) {
if (pat[s[head++]]-- >= 1) { cnt--; }
if (cnt == 0) { res.push_back(tail); }
if (head - tail == p.size() && pat[s[tail++]]++ >= 0) cnt++;
}
return res;
}
};
Minimum Window Substring
:::C++
class Solution {
public:
string minWindow(string s, string t) {
if (s.size() < t.size()) return string();
int p[256] = {0};
for (auto c: t) { p[c]++; }
int head = 0, tail = 0, cnt = t.size();
int hh = -1, tt = -1;
int min_len = INT_MAX;
while (head < s.size()) {
if (p[s[head++]]-- >= 1) { cnt--; }
while (cnt == 0) {
if (head - tail < min_len) {
min_len = head - tail;
hh = head;
tt = tail;
}
if (p[s[tail++]]++ >= 0) { cnt++; }
}
}
if (hh == -1) { return string(); }
return s.substr(tt, hh - tt);
}
};