LeetCode-Minimum Window Substring

中等难度的题目，

可是还是想不出来，

哎，这种题目应该属于必须做对的题目，

没有什么特别的考虑，只是给你设置了一个障碍，

需要你想办法翻越这个障碍，看了提示用两个指针，还是没做出来；

主要这种做法完全没有一点印象和灵感，还是锻炼和接触的太少了；

解法很简洁，只需要递进地移动开始指针就可以了，其实关键在于设计移动的策略和条件；

我发现其实一般简洁的解法当中都加入了一些对人来说显而易见的重复，我之前的想法一直是

在考虑移动起始点，然后再去判断是否可以满足包含的条件，这样就会很难处理，需要记录的各种

条件就会比较多；最后才发现其实保存前面已经满足条件的状态不变就行了，遇到新的元素之后，只需要

判断它是否可以取代前面的元素即可。

 1 class Solution {
 2 public:
 3     string minWindow(string S, string T) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         string res;
 7         if (S.size() < T.size()) {
 8             return res;
 9         }
10         vector<int> tvec(256, 0);
11         for (int i = 0; i < T.size(); ++i) {
12             ++tvec[T[i]];
13         }
14         vector<int> svec(256, 0);
15         int low = -1;
16         int high = S.size();
17         int count = 0;
18         for (int b = 0, e = 0; e < S.size(); ++e) {
19             if (tvec[S[e]] == 0) 
20                 continue;
21             if (svec[S[e]] < tvec[S[e]]) {
22                 ++count;
23             }
24             ++svec[S[e]];
25             if (count != T.size()) 
26                 continue;
27             b = findnext(S, svec, tvec, b);
28             if (e - b < high - low) {
29                 low = b;
30                 high = e;
31             }
32         }
33         if (low != -1) {
34             res = S.substr(low, high - low + 1);
35         }
36         return res;
37     }
38     int findnext(string &S, vector<int> &svec, vector<int> &tvec, int b) {
39         int i = b;
40         for (;i < S.size(); ++i) {
41             if (tvec[S[i]] == 0)
42                 continue;
43             if (svec[S[i]] <= tvec[S[i]])
44                 break;
45             --svec[S[i]];
46         }
47         return i;
48     }
49 };