题解 | #牛群名字覆盖#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目主要考察了字符串处理、滑动窗口、哈希表的运用。

题目解答方法的文字分析

我们可以使用滑动窗口的思想来解决这个问题。

具体步骤如下：

1. 首先，我们建立一个哈希表 targetFreq 来存储指定英文字母的频次。
2. 然后，使用双指针构建滑动窗口，左指针 left 和右指针 right，初始时都指向字符串 s 的第一个字符。
3. 初始化一个变量 minLen 用于记录最小子串的长度，一个变量 minSubstr 用于记录最小子串，以及一个变量 found 用于记录是否找到了包含所有指定英文字母的子串。
4. 开始滑动窗口，将右指针 right 向右移动，同时更新哈希表 currFreq 来记录当前窗口内各个字符的频次。
5. 当 currFreq 包含了 targetFreq 的所有字符且频次不少于 targetFreq 时，我们尝试将左指针 left 向右移动，以缩小子串长度，同时更新哈希表 currFreq。
6. 每次右指针 right 移动时，我们检查当前子串长度是否小于 minLen，如果是，则更新 minLen 和 minSubstr。
7. 最终，当滑动窗口结束时，minSubstr 就是最短的名字序列，使得这些名字能够包含所有指定的英文字母。

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> targetFreq;  // 存储指定英文字母的频次
        for (char c : t) {
            targetFreq[c]++;
        }

        unordered_map<char, int> currFreq;  // 当前窗口内各个字符的频次
        int left = 0, right = 0;  // 滑动窗口的左右指针
        int minLen = INT_MAX;  // 最小子串长度
        string minSubstr = "";  // 最小子串
        int found = 0;  // 是否找到了包含所有指定英文字母的子串

        while (right < s.length()) {
            char c = s[right];
            currFreq[c]++;

            // 当 currFreq 包含了 targetFreq 的所有字符且频次不少于 targetFreq 时
            while (found < targetFreq.size() && freqMet(currFreq, targetFreq)) {
                int len = right - left + 1;
                if (len < minLen) {
                    minLen = len;
                    minSubstr = s.substr(left, len);
                }

                char leftChar = s[left];
                currFreq[leftChar]--;
                if (currFreq[leftChar] < targetFreq[leftChar]) {
                    found--;
                }

                left++;
            }

            if (currFreq[c] == targetFreq[c]) {
                found++;
            }

            right++;
        }

        return minSubstr;
    }

private:
    bool freqMet(const unordered_map<char, int>& currFreq, const unordered_map<char, int>& targetFreq) {
        for (const auto& entry : targetFreq) {
            if (currFreq.find(entry.first) == currFreq.end() || currFreq.at(entry.first) < entry.second) {
                return false;
            }
        }
        return true;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！