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

文章目录

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

题目链接：

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

题目描述：

解法

暴力解法：

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

滑动窗口+哈希表：

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

1. left=0，right=0
2. 进窗口
3. 判断，出窗口
4. 更新结果

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;
    }
};

图解

例如：s = "cbaebabacd", p = "abc"

1. hash1[a]=1，hash1[b]=1，hash1[c]=1，m=3

   in=s[right]=c，++hash2[in - 'a']=2，hash[in - 'a']=2

   满足条件count++;right++

2. in=s[right]=b，++hash2[in - 'a']=2，hash[in - 'a']=2

   满足条件count++;right++

3. in=s[right]=a，++hash2[in - 'a']=2，hash[in - 'a']=2

   满足条件count++;right++

4. in=s[right]=e，窗口大小超过 m ，调整窗口out=s[left++]=e，++hash2[in - 'a']=2，hash[in - 'a']=1，不满足条件无法count++

   ，满足条件count--;right++

5. 依此类推