滑动窗口算法实战：水果成篮与最小覆盖子串

2. 使用数组模拟 hash 表

题目其实有提到 fruits[i] 的范围，所以我们不必真的使用 unordered_map 作为 hash 表，使用数组模拟即可，这样虽然会浪费空间，但是提高了效率。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100000] = { 0 };
        // cnt 用于统计 hash 表的水果的种类个数
        int n = fruits.size(), ret = 0, cnt = 0;
        for(int left = 0, right = 0; right < n; right++) {
            hash[fruits[right]]++;
            if(hash[fruits[right]] == 1) cnt++;
            while(cnt > 2) {
                hash[fruits[left]]--;
                if(hash[fruits[left++]] == 0) cnt--;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

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

题目描述：

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

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

解题思路

解法：滑动窗口 + 哈希

因为字符串 p 的异位词的长度一定于字符串 p 的长度相等，所以我们可以在字符串 s 中使用与字符串 p 等长度的滑动窗口来求解。

我们可以使用两个大小为 26 的数组来模拟哈希表，用于统计窗口内的字母频次和字符串 s 的字母频次，当比较得到两个哈希表相等时，说明滑动窗口中每种字母的数量与字符 p 每种字母的数量相同，窗口内的字符是字符 p 的一个异位词，此时记录窗口起始索引。

具体过程如下：

1. 初始化 left 和 right 指针来维护滑动窗口，两个大小为 26 的数组 hash1 和 hash2 来模拟哈希表，记录字符串 p 的字母频次和窗口字母频次。
2. right 向右遍历数组****right 位置的字母入窗口，将其加入哈希表。当滑动窗口长度大于字符串 p 的长度时，left++，将窗口左侧字母移除同时更新其在哈希表的频次。
3. 更新结果，当 hash1 与 hash2 相等时，记录窗口起始索引。

注意：判断两个 hash 表是否相等的时间复杂度较高，效率较低。故我们要优化更新结果的判断条件（两个哈希表相等），我们可以来使用一个变量 cnt 记录窗口内的字母相较于字符串 p 的有效字符的数量，并在入窗口和窗口时维护 cnt，这样更新结果时，只需判断 cnt 是否等于字符串 p 的长度就可以知道窗口字符是否是字符串 p 的异位词。

解释下有效字符的数量，其实就是让窗口的组成字母尽可能接近字符 p ，当有效字符的数量等于字符 p 的长度，就说明了窗口的字母频次与字符 p 的字母频次相等，这也是比较两个统计字母频次的哈希表相等的本质，cnt 间接完成了这个任务。

代码实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int n = s.size(), m = p.size();
        // 统计 p 字符串中每个字母出现的个数
        int hash1[26] = { 0 };
        for(auto ch : p) hash1[ch - 'a']++;
        // 统计窗口中每个字母出现的个数
        int hash2[26] = { 0 };
        // 统计窗口中有效字符的数量
        int cnt = 0;
        for(int left = 0, right = 0; right < n; right++) {
            // 进窗口 + 维护 cnt
            char in = s[right];
            hash2[in - 'a']++;
            if(hash2[in - 'a'] <= hash1[in - 'a']) cnt++;
            // 窗口长度大于字符串 p 的长度，窗口左端字母出窗口，
            // 并更新 cnt 和哈希表
            if(right - left + 1 > m) {
                char out = s[left++];
                // 出窗口 + 维护 cnt
                if(hash2[out - 'a'] <= hash1[out - 'a']) cnt--;
                hash2[out - 'a']--;
            }
            // 更新结果
            if(cnt == m) ret.push_back(left);
        }
        return ret;
    }
};

时间复杂度：O(n)

空间复杂度：O(1)

串联所有单词的子串

题目描述：

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

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

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

解题思路

解法：滑动窗口 + 哈希表

这道题就是找到字符串中所有字母异位词的升级版，从原来处理单个字符变成了处理单个单词，我们只需要将 words 的单词看成单个字母就行了，然后用滑动窗口 + 哈希表解决。

具体过程：

1. 用哈希表 hash1 记录 words 中每个单词的频次。
2. 遍历字符串 s，并用哈希表 hash2 来维护滑动窗口内的单词频次，注意每次增加窗口的大小为单词的长度。
3. 当窗口大小大于所有单词的总长度时，出窗口和更新 hash2。
4. 当 hash1 和 hash2 两个哈希表相等时，更新结果。

判断两个哈希表是否相等消耗较大，用 count 来优化，**count 统计滑动窗口内有效单词的个数。**当 count 与 words 的单词个数相等时，说明找到了符合条件的一个窗口。

代码实现

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1;
        for(auto& e : words) hash1[e]++;
        int len = words[0].size(), m = words.size(), n = s.size();
        // 执行 len 次滑动窗口
        for(int i = 0; i < len; ++i) {
            unordered_map<string, int> hash2;
            for(int left = i, right = i, count = 0; right <= n - len; right += len) {
                // 进窗口 + 维护 count
                string in(s.begin() + right, s.begin() + right + len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
                // 判断 + 出窗口 + 维护 count
                if(right - left + 1 > m * len) {
                    string out(s.begin() + left, s.begin() + left + len);
                    if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    left += len;
                }
                // 更新结果
                if(count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};

1. 执行 len 次滑动窗口（len 是单词长度）：由 s 字符串的长度不一定是单词长度的整数倍，需要执行 len 滑动窗口来保证答案的完整性。
2. 注意 right 的范围，right 最后一次执行循环的位置应该是在 n - len 处。

时间复杂度：O( n * len)，其中 n 是字符串 s 的长度，需要 len 次滑动窗口，每次遍历一次 s。

空间复杂度：O(m * len)，m 是单词个数，每次滑动窗口都需要用一个哈希表来存储单词频次。

最小覆盖子串

题目描述：

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

注意：

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

解题思路

解法：滑动窗口 + 哈希

根据题目，我们直接根据暴力解法来优化，就得到滑动窗口 + 哈希的解题方法。

具体过程如下：

1. 利哈希表 hash1 来统计字符串 t 中每个字符出现的频次。
2. 使用滑动窗口遍历字符串 s，并用哈希表 hash2 来统计窗口中字符频次。
3. 当窗口的字符频次满足要求时，更新结果，然后收缩窗口，直到窗口字符频次不满足要求。

注意：这里判断窗口的字符频次满足要求不是判断两个哈希表是否相等，而是 hash1 的字符频次要完整的出现在 hash2 中，hash1 中可以出现除字符串 t 中的字符以外的字符频次。也就是说，窗口内只要完整出现字符串 t 的所有字符即可（字符种类及其对应的频次）。

我们这里还是利用 count 来完成判断，这里的 count 统计的时有效字符的种类，只有 t 中的单个字符在窗口内出现的频次与在 t 中完全一样，count 才自增 1，同理，频次不相等时就自减 1，当 count 与 t 中字符种类数相同时，说明找到一个符合条件的覆盖字串，更新结果。

代码实现

class Solution {
public:
    string minWindow(string s, string t) {
        string ret;
        // hash1 统计 t 字符频次和计算 hash1 的大小，hash1size 统计 t 的字符种类
        int hash1[128] = { 0 }, hash1size = 0;
        for(auto e : t) if(hash1[e]++ == 0) hash1size++;
        // hash2 统计窗口字符频次
        int hash2[128] = { 0 };
        int len = INT_MAX, start = 0;
        // count 统计有效字符的种类
        for(int left = 0, right = 0, count = 0; right < s.size(); right++) {
            // 进窗口 + 维护 count
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;
            // 判断
            while(count == hash1size) {
                // 更新结果
                if(right - left + 1 < len) {
                    len = right - left + 1;
                    start = left;
                }
                // 出窗口 + 维护 count
                char out = s[left++];
                if(hash2[out]-- == hash1[out]) count--;
            }
        }
        ret = len == INT_MAX ? "" : s.substr(start, len);
        return ret;
    }
};

时间复杂度：O(n)

空间复杂度：O(1)