[leetcode_76]Minimum Window Substring

双指针，第一个指针开始指向第一个字符，从前往后枚举第二个指针的位置，如果覆盖所有目标字符，则滑动首指针，看看是否依然满足条件。求出最小区间即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


class Solution {
public:
    int letters1[256];
    int letters2[256];
    string minWindow(string S, string T) {
        for(int k = 0;k < 256;k++) {
            letters1[k] = 0;
            letters2[k] = 0;
        }
        for(int k = 0;k < T.length();k++) {
            letters1[T[k]]++;
            letters2[T[k]]++;
        }
        int min = S.length()+T.length();
        int start,end;
        int count = T.length();
        int i = 0;
        for(int j = 0;j < S.length();j++) {
            if(letters2[S[j]] > 0) {
                letters1[S[j]]--;
                if(letters1[S[j]] >= 0)count--;
            }
            if(count == 0) {
                while(true) {
                    if(letters2[S[i]] > 0) {
                        if(letters1[S[i]] < 0) 
                            letters1[S[i]]++;
                        else
                            break;
                    }
                    i++;
                }
                if(j - i + 1 < min) {
                    min = j - i + 1;
                    start = i;
                    end = j;
                }
            }
        }
        if(min == S.length()+T.length())return "";
        return string(S,start,end - start + 1);
    }
};