🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

       <<Git>><<MySQL>>

🌟心向往之行必能至

给定两个字符串 s 和 t，在 s 中找出包含 t 所有字符（包括重复字符）的最短子串。如果不存在，返回空字符串 ""。

核心思路：滑动窗口 + 哈希计数

这道题的核心是用滑动窗口动态维护一个区间，同时用 ** 哈希表（数组）** 来统计字符出现的次数，从而高效判断当前窗口是否满足条件。

完整代码实现

cpp

class Solution {
public:
    string minWindow(string s, string t) {
        int ans[128] = {0}; // 用数组模拟哈希表，统计t中各字符的需求
        int count = 0; // 记录还需要满足的不同字符种类数

        // 初始化：统计t中每个字符的出现次数
        for (auto ch : t) {
            if (ans[ch] == 0)
                ++count; // 每遇到一个新字符，种类数加1
            ++ans[ch];
        }

        int left = 0;
        int ans_left = -1, ans_right = s.size(); // 初始化答案区间为最大可能值

        // 右指针扩展窗口
        for (int right = 0; right < s.size(); ++right) {
            --ans[s[right]]; // 当前字符进入窗口，需求减1
            if (ans[s[right]] == 0) {
                --count; // 如果该字符的需求被完全满足，种类数减1
            }

            // 当窗口包含所有字符时，尝试收缩左指针以找到更小的窗口
            while (count == 0) {
                // 更新最小窗口
                if (right - left < ans_right - ans_left) {
                    ans_left = left;
                    ans_right = right;
                }

                // 左指针右移，缩小窗口
                if (ans[s[left]] == 0) {
                    ++count; // 如果移出的字符是刚好满足需求的，种类数加1
                }
                ++ans[s[left]];
                ++left;
            }
        }

        // 根据结果区间返回子串
        return ans_left == -1 ? "" : s.substr(ans_left, ans_right - ans_left + 1);
    }
};

代码逐行解析

1. 初始化阶段

cpp

int ans[128] = {0};
int count = 0;
for (auto ch : t) {
    if (ans[ch] == 0)
        ++count;
    ++ans[ch];
}

• ans 数组用来统计字符串 t 中每个字符的出现次数
• count 记录 t 中不同字符的种类数
• 遍历 t，初始化字符计数和种类数

2. 滑动窗口扩展

cpp

for (int right = 0; right < s.size(); ++right) {
    --ans[s[right]];
    if (ans[s[right]] == 0) {
        --count;
    }

• 右指针 right 向右移动，将当前字符加入窗口
• 对应字符的需求计数减 1
• 如果该字符的需求刚好被完全满足（计数变为 0），则待满足的种类数 count 减 1

3. 滑动窗口收缩

cpp

while (count == 0) {
    if (right - left < ans_right - ans_left) {
        ans_left = left;
        ans_right = right;
    }
    if (ans[s[left]] == 0) {
        ++count;
    }
    ++ans[s[left]];
    ++left;
}

• 当 count == 0 时，说明当前窗口已经包含了 t 的所有字符
• 此时尝试移动左指针 left，缩小窗口以寻找更短的满足条件的子串
• 在移动左指针前，先更新最小窗口的记录
• 如果移出的字符是刚好满足需求的（计数为 0），则待满足的种类数 count 加 1
• 最后将该字符的需求计数加 1，并移动左指针

4. 结果返回

cpp

return ans_left == -1 ? "" : s.substr(ans_left, ans_right - ans_left + 1);

• 如果 ans_left 仍为初始值 -1，说明没有找到满足条件的子串，返回空字符串
• 否则，返回从 ans_left 到 ans_right 的子串

复杂度分析

• 时间复杂度：\(O(m + n)\)。其中 m 是字符串 s 的长度，n 是字符串 t 的长度。每个字符最多被左右指针各访问一次。
• 空间复杂度：\(O(1)\)。因为我们用了一个固定大小为 128 的数组来存储字符计数，这是一个常数空间。