C++ 滑动窗口算法进阶解析与实战

解法二：滑动窗口 + 数组模拟哈希表

算法思路： 利用数组 hash 来代替哈希表，用水果种类的值直接作为数组下标，来统计每种水果的数量。这种方式效率更高，因为直接使用数组的下标访问比哈希表操作更快。

代码实现：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = {0}; // 数组模拟哈希表
        int ret = 0; // 记录结果
        int left = 0; // 左指针
        int kinds = 0; // 记录当前窗口内的水果种类数
        for (int right = 0; right < fruits.size(); ++right) {
            if (hash[fruits[right]] == 0) kinds++; // 新种类水果进入窗口
            hash[fruits[right]]++; // 统计数量
            // 当水果种类超过 2 时，收缩窗口
            while (kinds > 2) {
                hash[fruits[left]]--; // 移除左边水果
                if (hash[fruits[left]] == 0) kinds--; // 种类数量减少
                left++; // 左指针右移
            }
            ret = max(ret, right - left + 1); // 更新最大水果数量
        }
        return ret;
    }
};

复杂度分析：

• 时间复杂度：O(n)，每个元素最多被左右指针访问两次。
• 空间复杂度：O(n)，哈希表或数组最多存储 n 种水果的频次。

详细说明：

1. Iteration 1-3：Right 扩展到 2，窗口内只有一种水果 3，因此子数组为 [3,3,3]，长度为 3。
2. Iteration 4：加入水果 1，种类增加到两种，窗口变为 [3,3,3,1]，长度更新为 4。
3. Iteration 5：加入水果 2，种类增加到三种，此时需要调整窗口，移动 Left，直到只剩两种水果。经过调整，窗口变为 [1,2,1]。
4. Iteration 6-8：继续右移 Right，窗口内的水果种类保持为两种，最大长度更新为 5，子数组为 [1,2,1,1,2]。
5. Iteration 9-11：加入水果 3，水果种类再次超出限制，继续收缩窗口，最终找到的最大子数组长度为 5。

2.2 找到字符串中所有字母异位词

题目链接：438. 找到字符串中所有字母异位词

题目描述： 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。顺序可以不考虑。

异位词是指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1：

• 输入：s = "cbaebabacd", p = "abc"
• 输出：[0,6]
• 解释：起始索引为 0 的子串是 "cba"，它是 "abc" 的异位词。起始索引为 6 的子串是 "bac"，它是 "abc" 的异位词。

提示：

• 1 <= s.length, p.length <= 3 * 10^4
• s 和 p 仅包含小写字母。

解法：滑动窗口 + 哈希表

算法思路： 这道题要求我们在字符串 s 中找到所有与字符串 p 的 异位词 对应的子串。由于异位词由相同字母组成且长度与 p 相同，因此我们可以使用滑动窗口来解决这一问题。

1. 窗口大小固定：因为异位词的长度一定与字符串 p 的长度相同，所以我们构造一个长度为 p.size() 的滑动窗口，每次右移窗口，动态维护窗口内每个字母的出现频次。
2. 频次匹配判断：通过两个大小为 26 的数组来统计字母出现的次数，分别用于存储当前窗口内字母频次（hash2）和 p 中的字母频次（hash1）。当两个数组的内容相同，说明当前窗口就是 p 的一个异位词。
3. 优化判断：要判断窗口字符串是否是异位词，只需要判断同一种字符在两个字符串中出现的次数是否一样即可，这里使用 count 来统计有效字符的个数即可轻松判断。

代码实现：

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[26] = {0}; // 统计字符串 p 中每个字符出现的个数
        for (auto ch : p) hash1[ch - 'a']++;
        int hash2[26] = {0}; // 统计窗口里面的每一个字符出现的个数
        int m = p.size();
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right]; // 进窗口 + 维护 count
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if (right - left + 1 > m) { // 判断窗口是否需要收缩
                char out = s[left++]; // 出窗口 + 维护 count
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            // 更新结果
            if (count == m) ret.push_back(left);
        }
        return ret;
    }
};

复杂度分析：

• 时间复杂度：O(n)，每个字符最多被左右指针访问两次，因此时间复杂度为线性。
• 空间复杂度：O(1)，只需要常数级别的额外空间用于存储两个固定大小的数组。

详细说明：

1. Iteration 1-3：Right=0 到 Right=2，窗口内包含 [c, b, a]，它与 p="abc" 完全匹配，属于异位词，记录起始索引 0。
2. Iteration 4：Right=3，窗口内包含 [b, a, e]，字母 e 不在 p 中，因此当前窗口不是异位词。
3. Iteration 9：Right=8，窗口内包含 [b, a, c]，这再次是 p="abc" 的排列，属于异位词，记录起始索引 6。

2.3 串联所有单词的子串

题目链接：30. 串联所有单词的子串

题目描述： 给定一个字符串 s 和一个字符串数组 words，words 中所有字符串的长度相同。s 中的 串联子串 是指包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" 和 "efcdab" 都是串联子串，而 "acdbef" 不是串联子串，因为它不是 words 排列的连接。

返回所有串联子串在 s 中的开始索引，顺序可以不考虑。

示例 1：

• 输入：s = "barfoothefoobarman", words = ["foo","bar"]
• 输出：[0,9]
• 解释：子串 "barfoo" 的起始索引为 0，它是 words 中按顺序排列的连接。子串 "foobar" 的起始索引为 9，它是 words 中按顺序排列的连接。

提示：

• 1 <= s.length <= 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 仅包含小写英文字母。

解法：滑动窗口+哈希表

算法思路： 本题可以类比为寻找字符串中所有字母异位词的变种问题。不同的是，这里处理的对象是单词而不是单个字符。我们需要遍历字符串 s，并通过滑动窗口找到所有符合条件的单词排列。

1. 使用哈希表 hash1 记录 words 中每个单词的频次。
2. 遍历字符串 s，每次滑动窗口的大小为 words 中单词的总长度。
3. 在每个窗口内，维护另一个哈希表 hash2，用于记录当前窗口内单词的频次。
4. 当两个哈希表的内容一致时，说明当前窗口是一个符合要求的串联子串，记录其起始索引。同样采用 count 变量来统计有效字符串的个数进行优化。

代码实现：

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

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1; // 保存 words 中所有单词的频次
        for (auto& word : words) hash1[word]++;
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) { // 执行 len 次
            unordered_map<string, int> hash2; // 维护窗口内单词的频次
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len) {
                string in = s.substr(right, len); // 进窗口
                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in]) count++; // 判断是否需要缩小窗口
                if (right - left + 1 > len * m) {
                    string out = s.substr(left, len); // 出窗口
                    if (hash1.count(out) && hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    left += len;
                }
                // 更新结果
                if (count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};

复杂度分析：

• 时间复杂度：O(n * m * l)，其中 n 是字符串 s 的长度，m 是 words 中单词的个数，l 是单词的长度。
• 空间复杂度：O(m * l)，用于存储 words 中单词的哈希表以及滑动窗口中的哈希表。

2.4 最小覆盖子串

题目链接：76. 最小覆盖子串

题目描述： 给你一个字符串 s 和一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在这样的子串，则返回空字符串 ""。

注意：

• 对于 t 中重复的字符，最小子串中该字符数量必须不少于 t 中的字符数量。
• 如果存在这样的子串，答案是唯一的。

示例 1：

• 输入：s = "ADOBECODEBANC", t = "ABC"
• 输出："BANC"
• 解释：最小覆盖子串 "BANC" 包含字符串 t 的 'A'、'B' 和 'C'。

提示：

• 1 <= s.length, t.length <= 10^4
• s 和 t 由英文字母组成。

解法：滑动窗口 + 哈希表

算法思路： 这是一个典型的滑动窗口问题。目标是找到字符串 s 中能够覆盖 t 所有字符的最小子串。解决思路如下：

1. 滑动窗口的应用：使用两个哈希表，一个用来记录 t 中每个字符的频次，另一个用来动态维护滑动窗口中的字符频次。
2. 动态调整窗口大小：通过不断扩大窗口右边界，将字符加入窗口。一旦窗口内的字符满足 t 的要求，开始缩小窗口左边界，尽量缩短窗口长度。
3. 优化判断：使用 count 变量来统计有效字符，统计的是字符出现的种类。

代码实现：

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

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0}; // 记录字符串 t 中每个字符的频次
        int kinds = 0; // 统计 t 中不同的字符种类
        for (auto ch : t) {
            if (hash1[ch]++ == 0) kinds++;
        }
        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
            // 如果当前窗口满足条件，尝试收缩窗口
            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);
    }
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，滑动窗口遍历每个字符最多两次。
• 空间复杂度：O(1)，哈希表的大小固定为 128，存储字符频次。

总结

本文深入探讨了滑动窗口的高级应用，通过对一系列复杂问题的深度剖析，进一步展示了滑动窗口的灵活性与高效性。无论是「水果成篮」的双种类约束，还是「找到字符串中所有字母异位词」的字符频次比较，抑或是「串联所有单词的子串」的字符串匹配与「最小覆盖子串」的字符覆盖问题，这些问题都通过滑动窗口的精妙操作得到了优雅的解决。滑动窗口的核心在于对窗口边界的动态调整和哈希表的巧妙使用，结合不同场景的需求，展现了它在复杂算法挑战中的无限可能性。