leetcode 76. Minimum Window Substring

题目

给一个字符串s和t，求出包含t里面字母的 s的最小子串

题解

用一个map存这个字符在t串出现的次数，然后遍历s串，然后减去每个字母，如果当前map[char] 仍然大于0，那么说明当前这个char是在t中，我们将l2--
然后当l2 == 0 时候 说明已经找到符合要求的一个解，但是不一定是最小的。
因此我们用同样的方法，收缩st, 然后使得区间不断变小..
这样 算是双指针的一种应用了把

class Solution {
public:
    string minWindow(string s, string t) {
        int l1 = s.size();
        int l2 = t.size();
        unordered_map<char,int> mp;
        for (auto x : t)
            mp[x] ++;
        int i = 0, j = 0;
        int len = INT_MAX;
        int head = 0;
        while(j < l1) {
            if(--mp[s[j++]] >= 0) l2--;
            while(l2 == 0) {
                if (j - i < len) {
                    len = j-i;
                    head = i;
                }
                if(++mp[s[i++]] > 0) l2++;
            }
        }
        return len == INT_MAX ? "" : s.substr(head, len);
    }
};