【C++习题】14.滑动窗口_找到字符串中所有字母异位词

文章目录

- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
- 图解

题目链接：

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

题目描述：

768c1cb105db920f4a438da0e3135f4d

解法

暴力解法：

字母排序后运用滑动窗口解题。

滑动窗口+哈希表：

083e1fe9a56c3bdfc0f77ae19859c75a

我们可以优化一下，比如下面cba到bae，实际上只是把c去掉，加上一个e，没必要三个全删。

0e634a75ca56de9fb1f91b5d72b28b68

left=0，right=0
进窗口
判断，出窗口
更新结果

C++ 算法代码：

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']++;//遍历字符串 p，对每个字符出现的次数进行统计
        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
            //++hash2[in - 'a'] 先将 hash2[in - 'a'] 的值增加1，然后检查是否小于等于 hash1[in - 'a']。
			//如果 hash2[in - 'a'] 的值小于等于 hash1[in - 'a']，说明这个字符在 p 中出现次数至少与 s 中当前字符出现次数相同，
            //说明这是一个有效的匹配字符，count 增加。
            //如果s[right]是p里面没有的字母，那么++hash2[in - 'a']=2，hash1[in - 'a']=1，不满足条件
            //如果s[right]是p里面出现1次的字母，那么++hash2[in - 'a']=2，hash1[in - 'a']=2，满足条件
            //如果s[right]是p里面出现2次的字母，那么++hash2[in - 'a']=3，hash1[in - 'a']=3，满足条件
            if(++hash2[in - 'a'] <= hash1[in - 'a']) 
            {
                count++; //count 用于记录当前窗口中有效字符的数量（即与 p 中字符匹配的字符数量）
            }
            if(right - left + 1 > m) // 判断窗口大小超过 m 时，调整窗口
            {
                char out = s[left++];
                // 出窗口 + 维护 count
                //更新 hash2，如果移除后 hash2[out - 'a'] 的值小于等于 hash1[out - 'a']，说明移除的是一个有效匹配字符，count 减少。
               // hash2[out - 'a']-- 先检查 hash2 中对应字符的计数是否小于等于 hash1，然后再将 hash2 中对应字符的计数减少1。
				//如果 hash2 的计数小于等于 hash1，说明移除的字符是一个有效的匹配字符，count 减少。
                if(hash2[out - 'a']-- <= hash1[out - 'a']) 
                {
                    count--;
                }
            }
            // 更新结果
            //当 count 等于 m 时，说明当前窗口是一个字母异位词，记录起始索引 left
            if(count == m) 
            {
                ret.push_back(left);
            }
        }
        return ret;
    }
};