【优选算法篇】用滑动窗口解锁 5 大经典问题，轻松应对高频算法题（下篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

接上篇：【优选算法篇】滑动窗口的艺术：如何动态调整子区间解决复杂问题（中篇）-CSDN博客

引言：通过上篇文章带大家进一步探索“滑动窗口算法”，小试牛刀。接下来将让大家感受一下滑动窗口在解题中的更多妙处。

滑动窗口算法在校招中的重要性体现在以下几点：

1. 提高解题效率：滑动窗口能够将时间复杂度从 O(n²) 降低到 O(n)，帮助解决大规模数据问题，满足面试的时间要求。
2. 常见面试题：许多校招面试中的经典问题，如查找异位词、最长无重复子串、最小覆盖子串等，都可以使用滑动窗口算法高效解决。
3. 考察算法能力：掌握滑动窗口算法展示了应聘者的算法思维和问题优化能力，面试官往往通过这类问题评估候选人的编程能力。
4. 空间与时间的平衡：滑动窗口算法能够有效平衡时间和空间复杂度，是面试中考察高效代码的一个重要工具。

"滑动窗口算法进阶指南：从经典到创新的多种应用"

1. C++滑动窗口算法进阶详解

1.1 滑动窗口的基本概念

滑动窗口算法是处理动态数据流、查找符合条件的子序列或子数组问题时的一种非常高效的技巧。在基本的滑动窗口应用中，我们通常将窗口的大小固定或者通过某些条件来动态调整。本文将带你深入探讨滑动窗口算法的进阶用法，包括如何处理不同类型的滑动窗口问题、如何优化窗口的使用，以及一些常见的进阶问题和技巧。

1.2 滑动窗口进阶：滑动窗口的动态调整

在一些问题中，窗口的大小并不是固定的，而是需要根据某些条件来调整。这种情况下，滑动窗口的动态调整尤为重要。常见的动态调整窗口大小的情况有：

• 窗口大小固定：有些问题需要维护一个固定大小的窗口，找到符合条件的最优解。
• 窗口大小动态变化：根据某些条件（例如，满足某种约束条件）来动态调整窗口的大小。

2. 题目1：找到字符串中所有字母异位词

题目链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

• 统计目标字符串p的字符频率：
  • 使用hash2数组来统计字符串p中每个字符的出现次数。这里的hash2[ch - 'a']表示字符ch在p中出现的次数。
• 滑动窗口的概念：
  • 使用两个指针left和right来表示当前窗口的范围。right指针扩展窗口，left指针在窗口大小超过p的长度时收缩窗口。
  • 每次窗口大小为p的长度时，检查当前窗口是否为p的一个字母排列（即窗口中的字符频率是否与p的频率一致）。
• 窗口内字符频率维护：
  • 使用hash1数组来记录当前窗口内各字符的频率。
  • count变量用来统计窗口内符合条件的字符数。即，当窗口中某个字符的频率不超过p中该字符的频率时，count就增加。
• 滑动窗口的扩展与收缩：
  • right指针每次向右扩展，增加窗口大小。当窗口大小超过p的长度时，left指针开始向右收缩，确保窗口大小保持与p的长度一致。
  • 在扩展窗口时，如果某个字符的频率超过p中的频率，则不再增加count，反之则增加count。
• 更新结果：
  • 当窗口大小等于p的长度时，判断count是否等于p的长度。如果是，则说明当前窗口是p的一个字母排列，将窗口左端left的位置加入结果ret中。

2.2 示例代码：

class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ret;
        int len = p.size(), hash2[26] = { 0 };

        // 统计字符串p的字符频率
        for (auto ch : p)
        {
            hash2[ch - 'a']++; // hash2数组记录p中每个字符的频率
        }

        int hash1[26] = { 0 }; // hash1数组记录当前窗口中的字符频率
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            // 扩展窗口，增加右边的字符
            hash1[s[right] - 'a']++; // 当前字符进入窗口

            // 如果当前字符频率不超过p中该字符的频率，增加count
            if (hash1[s[right] - 'a'] <= hash2[s[right] - 'a'])
                count++;

            // 如果窗口大小超过了p的长度，开始收缩窗口
            if (right - left + 1 > len)
            {
                // 左边的字符出窗口，更新count
                if (hash1[s[left] - 'a'] <= hash2[s[left] - 'a'])
                    count--;
                hash1[s[left] - 'a']--; // 更新频率
                left++; // 左指针右移，收缩窗口
            }

            // 判断当前窗口是否符合条件，count等于p的长度
            if (count == len)
            {
                ret.push_back(left); // 记录符合条件的窗口的起始位置
            }
        }
        return ret;
    }
};

这段代码用于解决“在字符串s中查找所有与字符串p的字母排列相同的子串”问题，采用了滑动窗口算法和字符频率比较的方法。核心思路是通过滑动窗口在字符串s中遍历，并检查每个窗口内的字符频率是否与p的字符频率相匹配，从而找出所有的字母排列。

2.2.1 关键点解析

1. 字符频率统计：
   • hash2统计字符串p的字符频率，这一步确保我们知道p中每个字符的出现次数。
   • hash1用于记录滑动窗口内字符的频率。
2. 滑动窗口的维护：
   • 使用right指针扩展窗口，并不断更新窗口中的字符频率。
   • 使用left指针收缩窗口，确保窗口大小与p的长度一致。
3. 符合条件的窗口判断：
   • count用于统计当前窗口中符合条件的字符的数量。当count == len时，说明当前窗口是p的一个字母排列，可以记录下当前窗口的起始位置。

2.3 时间与空间复杂度

• 时间复杂度：
  • 每个字符只会被访问一次，因此时间复杂度为O(n)，其中n是字符串s的长度。
  • 窗口的大小始终控制在p的长度以内，right和left指针分别只遍历一次整个字符串，因此时间复杂度是O(n)。
• 空间复杂度：
  • 使用了两个大小为26的数组hash1和hash2来记录字符频率，因此空间复杂度是O(1)，即常数级别空间。

2.4 补充（可看可不看）

2.4.1 算法思路：

1. 字符频率统计

• 由于p中的字母异位词是p的排列组合，所以我们可以通过比较p和当前窗口内子串的字符频率来判断是否为字母异位词。为了高效地进行频率比较，使用了两个大小为26的数组：hash1和hash2。
• hash2用来存储字符串p中的字符频率。
• hash1用来存储当前滑动窗口内的字符频率。

2. 滑动窗口

• 使用两个指针left和right来表示当前窗口的左右边界。right指针向右移动，扩展窗口，left指针在窗口大小超过p的长度时向右移动，收缩窗口。
• 每当right指针移动时，将当前字符加入窗口并更新hash1数组。当窗口大小超过p的长度时，left指针向右收缩窗口，并更新hash1数组。

3. 字母异位词检查

• 在窗口大小等于p的长度时，通过check函数来判断当前窗口是否是p的字母异位词。check函数通过比较hash1和hash2数组来判断两者是否相同。如果相同，则说明当前窗口的字符频率与p一致，是一个字母异位词。

4. 返回结果

• 如果当前窗口是一个字母异位词，则将窗口的起始位置left加入结果数组ret中。

2.4.2 示例代码：

bool check(int hash1[26], int hash2[26]) {
    for (int i = 0; i < 26; i++) {
        if (hash1[i] != hash2[i]) {  // 如果有任何字符频率不匹配
            return false;  // 不是字母异位词
        }
    }
    return true;  // 字符频率完全匹配，是字母异位词
}

class Solution {
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ret;  // 用于保存结果
        int len = p.size(), hash2[26] = { 0 };

        // 统计字符串 p 的字符频率
        for (auto ch : p)
        {
            hash2[ch - 'a']++;  // 更新 p 中字符的频率
        }

        int hash1[26] = { 0 };  // 当前窗口的字符频率
        int left = 0;

        // 遍历字符串 s，使用滑动窗口
        for (int right = 0; right < s.size(); right++)
        {
            hash1[s[right] - 'a']++;  // 进入窗口的字符更新频率

            // 窗口大小超过 len，移除左端字符
            if (right - left + 1 > len)
            {
                hash1[s[left] - 'a']--;  // 左端字符出窗口，更新频率
                left++;  // 收缩窗口
            }

            // 当窗口大小等于 p 的长度时，检查是否为字母异位词
            if (right - left + 1 == len && check(hash1, hash2))
            {
                ret.push_back(left);  // 将符合条件的窗口起始位置加入结果
            }
        }
        return ret;  // 返回所有的字母异位词的起始位置
    }
};

详细解析

1. 初始化：
   • hash2数组用于存储字符串p的字符频率（每个字符减去'a'的值作为数组索引）。
   • hash1数组用于存储滑动窗口中字符的频率。
   • left和right指针初始化为0，表示滑动窗口的左右边界。
2. 滑动窗口的核心：
   • right指针从左至右遍历字符串s，每次扩展窗口，更新窗口内字符的频率。
   • 当窗口的大小超过了p的长度时，left指针开始右移，收缩窗口，移除左端的字符。
3. 检查字母异位词：
   • 当窗口大小恰好等于p的长度时，调用check函数比较hash1和hash2。如果它们相等，说明当前窗口是p的一个字母异位词。
4. 返回结果：
   • 如果当前窗口是一个字母异位词，则将left（窗口的起始位置）加入结果ret中。
   • 最后返回ret，即所有满足条件的子串的起始位置。

时间复杂度分析

• 时间复杂度：O(n)，其中n是字符串s的长度。每个字符在right指针移动时被访问一次，且每次只进行常数时间的操作（更新字符频率和窗口边界）。因此，整体时间复杂度为O(n)。
• 空间复杂度：O(1)，即使用了两个固定大小的数组hash1和hash2，大小为26（即字母表的大小），因此空间复杂度为O(1)，不随输入规模增加而增长。

2.4.3 总结：

这段代码利用滑动窗口和字符频率统计的技巧，能够在O(n)的时间内高效地找到字符串s中所有与字符串p字母排列相同的子串。通过维护窗口内的字符频率并与目标字符串p的频率进行比较，能够实现快速判断字母异位词的功能。

2.5 总结：

这段代码通过滑动窗口和字符频率统计相结合的方式，在字符串s中高效地找到所有与p的字母排列相同的子串。通过维护窗口内字符的频率，并与目标字符串p的频率进行对比，能够在O(n)的时间复杂度内解决问题，适用于大规模数据的处理。

3. 题目2：串联所有单词的子串

题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

3.1.1 算法步骤

1. 构建目标频次表 hash2
   • 使用一个哈希表 hash2 存储 words 中每个单词的频次，用于快速验证某个窗口是否满足条件。
2. 滑动窗口遍历字符串
   • 对于每个可能的起始偏移量 i（从 0 到 len - 1），分别维护一个滑动窗口。
   • 使用两个指针 left 和 right 表示当前窗口的左右边界，窗口中每次扩展的步长为单词长度 len。
3. 窗口扩展（right 指针向右移动）
   • 从字符串中提取长度为 len 的子串 in。
   • 更新窗口中单词的频次计数表 hash1。
   • 如果 in 在 hash2 中，且频次未超标，则增加计数 count。
4. 窗口收缩（left 指针向右移动）
   • 如果窗口大小超过了 len * m，从 left 开始收缩窗口。
   • 从窗口中移除最左边的单词 out，更新 hash1 和 count。
5. 检查窗口是否满足条件
   • 当 count == m 时，说明窗口中包含了 words 中所有单词，记录当前 left 为起始索引。
6. 返回结果
   • 遍历完所有偏移量后，返回符合条件的起始索引列表。

3.2 示例代码：

class Solution
{
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        vector<int> ret; // 存储结果，即所有符合条件的起始索引
        unordered_map<string, int> hash2; // 目标频次表，存储 words 中每个单词的频次

        // 构建目标频次表 hash2
        for (auto& ch : words) {
            hash2[ch]++; // 统计每个单词在 words 中的频次
        }

        int len = words[0].size(); // 单词的长度
        int m = words.size();      // 单词的数量

        // 遍历所有可能的起始偏移量 i（从 0 到 len - 1）
        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash1; // 当前窗口内的频次表
            int left = i, right = i, count = 0; // 初始化滑动窗口的左右指针和有效单词计数

            // 滑动窗口遍历字符串
            while (right + len <= s.size()) {
                // 窗口右端扩展，提取单词 in
                string in = s.substr(right, len);
                hash1[in]++; // 更新当前窗口的频次表

                // 如果 in 在目标频次表中，且未超出目标频次，则增加有效单词计数
                if (hash1[in] <= hash2[in]) {
                    count++;
                }

                // 如果窗口大小超过 len * m，则需要收缩窗口
                if (right - left >= len * m) {
                    string out = s.substr(left, len); // 窗口左端单词
                    if (hash1[out] <= hash2[out]) {
                        count--; // 如果 out 是有效单词，则减少有效计数
                    }
                    hash1[out]--; // 从窗口中移除 out
                    left += len;  // 窗口左端右移
                }

                // 如果有效单词计数等于单词总数，说明当前窗口符合条件
                if (count == m) {
                    ret.push_back(left); // 记录当前窗口的起始索引
                }

                // 窗口右端右移
                right += len;
            }
        }

        return ret; // 返回结果
    }
};

3.2.1 详细注释说明

1. 构建目标频次表 hash2：

for (auto& ch : words) { hash2[ch]++; }

• 这部分统计了 words 中所有单词的出现频次，存储在 hash2 中，用于验证窗口中的单词频次是否符合要求。

2. 遍历所有偏移量：

for (int i = 0; i < len; i++) {

因为每个单词长度固定为 len，所以需要从 0 到 len - 1 依次作为起始偏移量，确保所有可能的窗口都能被覆盖。

3. 滑动窗口逻辑：

• 窗口扩展：

string in = s.substr(right, len); hash1[in]++; if (hash1[in] <= hash2[in]) { count++; }

• 每次扩展窗口时，提取右端单词 in，更新窗口内的频次表 hash1，并根据是否符合目标频次表 hash2 更新有效单词计数。
• 窗口收缩：

if (right - left >= len * m) { string out = s.substr(left, len); if (hash1[out] <= hash2[out]) { count--; } hash1[out]--; left += len; }

当窗口大小超过 len * m 时，收缩窗口，移除左端单词 out 并更新频次表和有效单词计数。

• 检查条件：

if (count == m) { ret.push_back(left); }

当有效单词计数等于单词总数时，说明窗口内的单词频次完全匹配，记录当前起始索引。

3.2.2 算法核心

1. 双哈希表：hash2 用于存储目标频次，hash1 用于动态维护窗口内的单词频次。
2. 滑动窗口：动态调整窗口大小，使得所有单词能被检查而无需重复计算。
3. 偏移量遍历：确保所有起始位置的可能性都能被覆盖。

3.3 时间与空间复杂度

1. 时间复杂度：
   • 外层循环：len 次（单词长度）。
   • 内层滑动窗口：O(n / len) 次（每次移动 len 个字符）。
   • 总复杂度：O(len * n / len) = O(n)。
2. 空间复杂度：
   • hash2 和 hash1 大小为 O(m)，m 是单词数量。
   • 总复杂度：O(m)。

3.4 补充（可看可不看）

3.4.1 暴力解法

示例代码：

class Solution
{
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        vector<int> ret;
        if (words.empty() || s.empty()) return ret;

        int len = words[0].size();   // 每个单词的长度
        int m = words.size();        // 单词的总个数
        int totalLen = len * m;      // 所有单词串联后的总长度

        unordered_map<string, int> wordCount; // 构建目标频次表
        for (const string& word : words) 
        {
            wordCount[word]++;
        }

        for (int i = 0; i <= s.size() - totalLen; i++) 
        { // 枚举每个可能的起始位置
            unordered_map<string, int> seen;            // 当前窗口内的频次表
            int j = 0;
            for (; j < m; j++) {
                string word = s.substr(i + j * len, len); // 提取一个单词
                if (wordCount.find(word) != wordCount.end())
                {
                    seen[word]++;
                    if (seen[word] > wordCount[word])
                    { // 如果当前单词超出频次，匹配失败
                        break;
                    }
                }
                else 
                { // 当前单词不在 words 中，匹配失败
                    break;
                }
            }
            if (j == m)
            { // 如果成功匹配了所有单词
                ret.push_back(i);
            }
        }
        return ret;
    }
};

代码解析

1. 初始化

int len = words[0].size(); // 单词长度 int m = words.size(); // 单词个数 int totalLen = len * m; // 子串的总长度

• 计算所有单词串联后的总长度 totalLen。

2. 构建目标频次表

unordered_map<string, int> wordCount; for (const string& word : words) { wordCount[word]++; }

• 使用 wordCount 记录 words 中每个单词的频次。

3. 遍历起始索引

for (int i = 0; i <= s.size() - totalLen; i++) { unordered_map<string, int> seen; int j = 0; ... }

• 枚举字符串 s 的每个可能的起始索引 i。
• 对于每个 i，维护一个哈希表 seen，记录从当前位置开始的单词频次。

4. 检查子串

string word = s.substr(i + j * len, len); // 提取一个单词 if (wordCount.find(word) != wordCount.end()) { seen[word]++; if (seen[word] > wordCount[word]) break; // 频次超出，匹配失败 } else { break; // 单词不在目标频次表中，匹配失败 }

• 从 i 开始，每次提取一个长度为 len 的子串 word。
• 如果 word 不在 words 中，或频次超出，匹配失败。

5. 匹配成功

if (j == m) ret.push_back(i);

• 如果从 i 开始的子串匹配了所有单词，记录起始索引 i。

暴力解法思路

1. 枚举字符串 s 的每一个可能的起始索引 i。
2. 从索引 i 开始，尝试匹配 words 中的所有单词：
   • 每次取出一个长度为 len 的子串，检查是否在 words 中。
   • 用一个哈希表记录已匹配的单词及其频次。
3. 如果匹配成功，将 i 加入结果。

暴力解法的关键

• 对于每个起始位置，检查以此位置为起点的子串是否正好包含 words 中所有单词的一个排列。
• 因为每个起点的检查独立进行，时间复杂度较高。

3.4.2 时间与空间复杂度

复杂度分析

时间复杂度

• 外层循环遍历 s 的每个起始索引，共运行 O(n - totalLen) 次。
• 内层循环检查 m 个单词，每个单词检查需要 O(len)。
• 总时间复杂度： O((n−totalLen)×m×len)=O(n×m×len)

空间复杂度

• wordCount 和 seen 的大小为 O(m)。
• 空间复杂度：O(m)。

优缺点

优点

• 实现简单，易于理解。
• 不需要复杂的数据结构。

缺点

• 时间复杂度较高，对于较长的字符串 s 或较多的单词，效率较低。

3.4.3 总结：

暴力解法适用于数据规模较小的情况，或作为初学者理解问题的第一步。如果 s 很长或 words 包含很多单词，建议使用优化的滑动窗口解法。

3.5 总结：

通过此题，能够学会如何高效地在字符串中进行子串匹配，掌握滑动窗口的思想，进而应用于更多复杂的问题。

对比两种解法

4. 题目3：最小覆盖子串

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

题目描述：

4.1 算法思路:

通过两个指针（left 和 right）维护一个窗口范围，在窗口内统计字符频次，并动态调整窗口的大小。

关键思想

1. 使用两个数组 hash1 和 hash2：
   • hash1：统计字符串 t 中每个字符的频次。
   • hash2：统计当前窗口中每个字符的频次。
2. 维护三个关键变量：
   • kinds：表示字符串 t 中有多少种不同的字符。
   • count：当前窗口中满足条件的字符种类数。
   • minlen 和 begin：记录最短的窗口长度和起始位置。
3. 滑动窗口：
   • 右移 right 扩大窗口，更新窗口内字符频次。
   • 当窗口中所有字符的频次满足 hash1 的要求时（count == kinds），进入收缩窗口阶段。
   • 左移 left 收缩窗口，尝试找到更短的子串。

4.2 示例代码：

//版本1：通过count判断
class Solution
{
public:
    string minWindow(string s, string t) 
    {
        int hash1[128] = { 0 }; // 用于统计字符串 t 中每个字符的频次
        int kinds = 0; // 表示字符串 t 中有多少种不同的字符
        for (auto ch : t) // 遍历字符串 t，初始化 hash1 和 kinds
        {
            if (hash1[ch]++ == 0) kinds++; // 如果是新字符（频次从 0 变为 1），增加种类计数
        }
        
        int hash2[128] = { 0 }; // 用于统计当前窗口内每个字符的频次
        int minlen = INT_MAX;   // 最短窗口的长度，初始化为最大值
        int begin = -1;         // 最短窗口的起始位置
        int count = 0;          // 当前窗口内满足条件的字符种类数

        // 滑动窗口：右指针 `right` 不断扩展窗口
        for (int left = 0, right = 0; right < s.size(); right++)
        {
            char in = s[right]; // 当前进入窗口的字符
            if (++hash2[in] == hash1[in]) count++; // 如果窗口内该字符的频次正好达到要求，增加 count

            // 如果窗口内的字符频次满足所有条件，尝试收缩窗口
            while (count == kinds) 
            {
                // 更新结果，如果当前窗口长度更短
                if (right - left + 1 < minlen) 
                {
                    minlen = right - left + 1; // 更新最短窗口的长度
                    begin = left;             // 记录最短窗口的起始位置
                }

                char out = s[left++]; // 当前从窗口移除的字符
                if (hash2[out]-- == hash1[out]) count--; // 如果移除的字符导致频次不再满足条件，减少 count
            }
        }

        // 如果没有找到符合条件的窗口，返回空字符串；否则返回最短窗口
        if (begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};

//版本2：通过check判断
bool check(int hash1[126],int hash2[126])
{
    for(int i=0;i<126;i++)
    {
        if(hash2[i]<hash1[i])
        {
            return false;
        }
    }
    return true;
}

class Solution 
{
public:
    string minWindow(string s, string t)
    {
        int hash1[126]={0};//保存字符串t中的每个单词的频次
        for(auto& ch: t)
        {
            hash1[ch]++;
        }
        int begin=-1,minlen=INT_MAX;
        int hash2[126]={0};
        for(int left=0,right=0;right<s.size();right++)
        {
            string s1="";
            hash2[s[right]]++;//进窗口
            while(check(hash1,hash2))
            {
                if(right-left+1<minlen)
                {
                    begin=left;
                    minlen=right-left+1;
                }
                hash2[s[left++]]--;
            }
        }
        if(begin==-1)  return "";
        else{
            return s.substr(begin,minlen);
        }
    }
};

4.2.1 代码解析

初始化

int hash1[128] = { 0 }; // 统计字符串 t 中每个字符的频次 int kinds = 0; // 有效字符的种类数 for (auto ch : t) if (hash1[ch]++ == 0) kinds++;

• hash1 初始化后，记录了字符串 t 中每个字符的频次。
• kinds 表示 t 中有多少种不同的字符。

滑动窗口逻辑

int hash2[128] = { 0 }; // 统计窗口内每个字符的频次 int minlen = INT_MAX, begin = -1; for (int left = 0, right = 0, count = 0; right < s.size(); right++) { char in = s[right]; if (++hash2[in] == hash1[in]) count++; // 进窗口时，更新 count

• 遍历字符串 s，右移 right 指针扩展窗口。
• hash2[in] == hash1[in] 时，说明该字符在窗口中满足频次要求，增加 count。

收缩窗口逻辑

while (count == kinds) { // 当所有字符种类都满足时，收缩窗口 if (right - left + 1 < minlen) { // 更新最短窗口 minlen = right - left + 1; begin = left; } char out = s[left++]; if (hash2[out]-- == hash1[out]) count--; // 出窗口时，更新 count }

• 当 count == kinds 时，说明当前窗口已经包含了 t 中所有字符。
• 检查当前窗口长度是否比记录的最小长度更小，若是，则更新结果。
• 左移 left 指针收缩窗口，尝试找到更短的子串。
• 如果某字符的频次不再满足要求（hash2[out]-- == hash1[out]），count--。

返回结果

if (begin == -1) return ""; // 如果没有找到满足条件的子串，返回空字符串 else return s.substr(begin, minlen); // 返回最短窗口

• 如果 begin 没有更新，说明没有找到符合条件的子串，返回空字符串。
• 否则，返回从位置 begin 开始、长度为 minlen 的子串。

4.3 时间与空间复杂度

1. 时间复杂度：
   • 外层循环遍历字符串 s 的长度，时间复杂度为 O(n)。
   • 内层循环的 while 最多遍历字符串 s 的长度一次，整体时间复杂度为 O(n)。
   • 总时间复杂度为 O(n)，其中 n 是字符串 s 的长度。
2. 空间复杂度：
   • 使用了两个大小为 128 的数组 hash1 和 hash2（固定大小），空间复杂度为 O(1)。

运行过程：

1. 初始化：
   • hash1 = {A: 1, B: 1, C: 1}，kinds = 3。
   • hash2 = {}，count = 0。
2. 滑动窗口：
   • right = 0，s[right] = A，hash2 = {A: 1}，count = 1。
   • right = 1，s[right] = D，hash2 = {A: 1, D: 1}，count = 1。
   • ...
   • right = 9，s[right] = C，hash2 = {A: 1, B: 1, C: 1}，count = 3。
3. 收缩窗口：
   • left = 0，窗口 [A, D, O, B, E, C]，长度更新为 6。
   • ...
   • 收缩到 [B, A, N, C]，更新最小窗口为 "BANC"。
4. 最终结果：
   • 返回 "BANC"。

优点

1. 高效性：
   • 时间复杂度为 O(n)，适合处理大规模字符串。
   • 使用滑动窗口技术，避免了暴力枚举所有子串。
2. 逻辑清晰：
   • 通过两个指针维护窗口，动态调整窗口大小。
   • 使用两个数组统计字符频次，简单高效。

4.4 补充（可看可不看）

4.4.1 暴力解法

示例代码：

class Solution
{
public:
    string minWindow(string s, string t)
    {
        int minLen = INT_MAX; // 最小子串长度
        string result = "";   // 记录结果

        // 遍历所有子串
        for (int i = 0; i < s.size(); i++)
        {
            for (int j = i; j < s.size(); j++)
            {
                // 截取子串 [i, j]
                string sub = s.substr(i, j - i + 1);

                // 检查子串是否包含 t
                if (contains(sub, t))
                {
                    if (sub.size() < minLen)
                    {
                        minLen = sub.size();
                        result = sub;
                    }
                }
            }
        }

        return result;
    }

    // 检查子串 sub 是否包含 t
    bool contains(string& sub, string& t)
    {
        unordered_map<char, int> freqT; // 统计 t 的字符频次
        unordered_map<char, int> freqSub; // 统计 sub 的字符频次

        for (char ch : t) freqT[ch]++;
        for (char ch : sub) freqSub[ch]++;

        for (auto& pair : freqT)
        {
            if (freqSub[pair.first] < pair.second) return false;
        }

        return true;
    }
};

算法流程

1. 双重遍历枚举子串：
   • 使用两层嵌套循环枚举字符串 s 的所有可能子串。
   • 外层循环确定子串的起始位置 i，内层循环确定子串的结束位置 j。
2. 截取子串：
   • 使用 s.substr(i, j - i + 1) 提取从位置 i 到位置 j 的子串。
3. 检查子串是否满足条件：
   • 使用辅助函数 contains 判断当前子串是否包含 t 中所有字符及其频次要求。
   • contains 中通过哈希表记录 t 和子串的字符频次，逐一比较是否满足条件。
4. 更新最小子串：
   • 如果当前子串满足条件，比较其长度是否小于 minLen，如果更短，则更新结果。
5. 返回结果：
   • 如果没有找到满足条件的子串，返回空字符串。
   • 否则返回结果字符串。

4.4.2 复杂度分析

1. 时间复杂度：
   • 枚举所有子串需要 O(n^2)。
   • 每次检查子串是否包含 t 的字符频次需要 O(m)，其中 m 是字符串 t 的长度。
   • 总时间复杂度为 O(n^2 * m)，适合小规模输入。
2. 空间复杂度：
   • 使用了两个哈希表统计字符频次，空间复杂度为 O(k)，其中 k 是字符串中不同字符的数量。

4.4.3 暴力解法的优缺点

优点：

1. 实现简单，易于理解。
2. 不需要复杂的算法技巧，直接枚举所有可能性。

缺点：

1. 性能低下，时间复杂度为 O(n^2 * m)，无法处理较大规模的输入。
2. 随着输入规模增大，运行时间呈指数增长，不实用。

4.4.4 总结：

暴力解法适用于简单场景，但由于其复杂度较高，仅在输入规模较小时可用。实际应用中推荐使用滑动窗口算法（时间复杂度 O(n)）。

4.5 总结：

这段代码实现了一个高效、逻辑清晰的滑动窗口算法，能够快速解决最小覆盖子串问题。

5. 最后

通过上述「找到字符串中所有字母异位词」、「串联所有单词的子串」及「最小覆盖子串」的例子，可以总结出滑动窗口算法的核心思想、应用场景和优化技巧。滑动窗口通过动态调整左右指针，在遍历数组时灵活地扩展和收缩窗口，避免了暴力解法中不必要的重复计算，使得许多问题的时间复杂度从 O(n^2) 或更高，优化到 O(n)。它在处理涉及连续子数组或子串的查找、统计、优化问题时，具有非常高的效率和空间优势，是解决此类问题的强大工具。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！