当前位置：首页 > article >正文

滑动窗口篇——如行云流水般的高效解法与智能之道（3）

article 2024/11/27 13:12:32

前言：

上篇我们介绍了滑动窗口的进阶练习，本篇难度继续升级，同样结合具体题目，帮助大家进一步掌握和运用滑动窗口。

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

题目链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题目分析：

题目要求返回所有异位词的起始索引，我们首先来了解什么是异位词和起始索引。

异位词：

1. 观察其示例可知，两个字符串的长度和所含字母相同

2. 字母的排列顺序不同

起始索引：该异位词的首字母在原先的字符串中的下标。

思路讲解：

首先可以考虑使用哈希表进行字符串的匹配问题:

字符匹配：

1. 首先用hash2对字符串p中的字符进行一一存储映射

2. 对s中将要匹配的字符串同样进行哈希映射处理

3. 如果两个哈希表完全相同，则该哈希表存储的字符串即为一个异位词

不难发现，在向后遍历进行存储时，为一个连续的区间，因此同样可尝试使用滑动窗口解决。

滑动窗口：

1. 定义都为0的left和right，right向后遍历的同时进行哈希映射存储，即为进窗口操作。

2. 当窗口长度大于字符串p的长度时，此处绝对不可能为异位词，因此需要left向后遍历的同时更改哈希映射存储，即为出窗口操作。

3. 当窗口长度与p的长度相等时，即可进行上面提到的字符匹配操作，如果成功匹配，则在vector数组ret中尾插中left的索引，反之则继续进行滑动窗口操作。

算法优化：

问题：每次字符匹配时，都需要进行26次的判断操作，虽然次数不算多，但在字符串长度较大时，仍会造成较大的时间损耗，那么我们该如何进行优化呢？

解答：大量时间损耗产生的原因是因为冗余的字符匹配，我们可以通过字符计数的方式进行匹配。

1. 异位词的基本要求就是长度相等，另外还需要出现的所有字母次数相同。

2. 我们可以把字符串p的长度记录为m，窗口内有效字母数记为count。

3. 入窗口时的哈希映射记录为in,当入窗口操作时，如果hash1[in]<=hash2[in]，说明进入了一个有效字母，count++。

4. 出窗口时的哈希映射记录为out，当出窗口操作时，如果hash2[out]<=hash2[out]，说明失去了一个有效字母,count--。

5. 当count与m相等时，代表两个字符串的有效字母也相等，此时一定为异位词，直接在vector数组ret中尾插left的索引即可。

代码实现：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash2[26]={0};//模拟哈希匹配字符串p
        int hash1[26]={0};//模拟哈希表记录窗口内的元素情况
        int m=p.size();//记录p的长度
        vector<int> ret;
        for(auto e:p)
        {
           hash2[e-'a']++;
        }//存储p中字母出现的次数
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            
            char in=s[right];//进窗口的元素
            if(++hash1[in-'a']<=hash2[in-'a'])
            {
                count++;
            }//进窗口同时维护count
            if(right-left+1>m)
            {
                char out=s[left++];
                if(hash1[out-'a']--<=hash2[out-'a'])
                {
                    count--;
                }
            }//出窗口的同时维护count
            if(count==m)
            {
                ret.push_back(left);
            }

        }
        return ret;
        
    }
};