567. 字符串的排列（c++）滑动窗口

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"

输出：true

解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"

输出：false

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

初始化哈希表：两个向量 hashmap1 和 hashmap2 被初始化为大小为26，所有元素的初始值都为0。这些向量用于计算字符串 s1 和 s2 中每个字符的出现次数

vector<int> hashmap1(26, 0);

vector<int> hashmap2(26, 0);

检查长度：比较 s1 和 s2 的长度。如果 s1 的长度大于 s2 的长度，则函数返回 false。这是因为如果 s1 比 s2 长，那么 s1 不能是 s2 的排列

int n = s1.size();

int m = s2.size();

if (n > m) {

   return false;

}

计算字符出现次数：遍历字符串 s1 和 s2，使用哈希表 hashmap1 和 hashmap2 计算每个字符的出现次数。

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

   hashmap1[s1[i] - 'a']++;

   hashmap2[s2[i] - 'a']++;

}

比较哈希表：在计算出现次数后，代码比较了两个哈希表。如果它们相等，那么意味着 s1 是 s2 的排列，因此函数返回 true。

if (hashmap1 == hashmap2) {

   return true;

}

滑动窗口技术：如果字符串的长度相等但哈希表不相等，则使用滑动窗口技术来检查排列。窗口大小为 n，即 s1 的长度。代码遍历 s2，更新窗口的哈希表并将其与 hashmap1 进行比较。如果它们在任何时候相等，函数返回 true

for (int i = n; i < m; ++i) {

   hashmap2[s2[i] - 'a']++;

   hashmap2[s2[i - n] - 'a']--;

   if (hashmap1 == hashmap2) {

       return true;

   }

}

具体代码如下：

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
    vector<int> hashmap1 (26, 0);
    vector<int> hashmap2 (26, 0);
    int n = s1.size();
    int m = s2.size();
    if(n>m){
        return false;
    }
    for (int i = 0; i < n; ++i) {
        hashmap1[s1[i]-'a']++;
        hashmap2[s2[i]-'a']++;
    }
    if (hashmap1 == hashmap2) {
        return true;
    }
    for (int i = n; i < m; ++i) {
        hashmap2[s2[i]-'a']++;
        hashmap2[s2[i - n]-'a']--;
        if (hashmap1 == hashmap2) {
            return true;
        }
    }
    return false;}
};