题解 | #寻找完成任务所需最短时间#

知识点

hash，双指针

思路

由于我们需要在s中找到最小连续子串res来满足t中的每个字母都在res中出现过，且重复字母出现次数也要保证子串中该字符的数量必须不少于 t 字符串中该字符的数量。

所以，我们可以用两个map建立从char到int的映射a、b，用于记录t和res的每个字符出现次数。对于s，我们可以用双指针来维护res。

我们先编写一个函数用于检查当前res是否合法，显然需要遍历a的每一位，并在b中检测是否满足b.second>=a.second的合法关系（即res中当前字符出现次数大于t中当前字符出现次数）

 bool check(map<char, int>a, map<char, int>b) {
        for (auto v : a) {
            if (b[v.first] < v.second)return false;
        }
        return true;
    }

然后假定i为res左端点，j为res右端点，这两个是临时端点，不断右移j并更新b，若b合法，则尝试右移i，若i向右移动后仍合法，则可以右移，以达到缩减子串长度的目的。

对每个合法状态，维护最小的i-j+1，即为子串长度，若需要更新，则同步更新ii与jj，用于复原最终需要返回的答案字符串。

代码c++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param t string字符串
     * @return string字符串
     */
    bool check(map<char, int>a, map<char, int>b) {
        for (auto v : a) {
            if (b[v.first] < v.second)return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        // write code here
        map<char, int>a;
        map<char, int>b;
        for (int i = 0; i < t.size(); i++) {
            a[t[i]]++;
        }
        int i = 0, j = 1;
        int ans = 1000000;
        b[s[0]]++;
        bool flag = 0;
        int ii, jj;
        for (; j < s.size(); j++) {
            b[s[j]]++;
            if (check(a, b)) {
                while (b[s[i]] > a[s[i]]) {
                    b[s[i]]--;
                    i++;
                    flag = 1;
                }
                if (j - i + 1 < ans) {
                    ii = i;
                    jj = j;
                    cout << i << " " << j << endl;
                    ans = j - i + 1;
                }

            }
        }
        string res = "";
        if (!flag)return res;
        else {
            for (int k = ii; k <= jj; k++)res += s[k];
            return res;
        }

    }
};