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

知识点

双指针 计数

思路

同向双指针，并维护两段指针之间的字母的计数，双指针每次右指针移动一次，左指针不断试探下一个位置是否可以，每次找到满足条件的最近的左指针。

时间复杂度

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return string字符串
     */
    string minWindow(string s, string t) {
        vector<int> cnt(60, 0), need(60, 0);
        for (auto c : t) {
            need[get(c)] += 1;
        }

        auto check = [&]() {
            for (int i = 0; i < 52; i ++) {
                if (cnt[i] < need[i]) return false;
            }
            return true;
        };

        auto test = [&](int x) {
            cnt[get(s[x])] -= 1;
            auto res = check();
            cnt[get(s[x])] += 1;
            return res;
        };

        int n = s.size();
        string res;
        for (int i = 0, j = 0; i < n; i ++) {
            cnt[get(s[i])] += 1;
            while (j < i and test(j)) {
                cnt[get(s[j])] -= 1;
                j ++;
            }
            if (check() and (res.empty() or res.size() > i - j + 1)) res = s.substr(j, i - j + 1);
        }
        return res;
    }
    int get(char c) {
        if (c >= 'a' and c <= 'z') return c - 'a';
        return c - 'A' + 26;
    }
};