初识算法 · 滑动窗口(3)

本文的主题是滑动窗口，通过两道题目讲解，一道是水果成篮，一道是找到字符串中的所有字母异位词。链接分别为：904. 水果成篮 - 力扣（LeetCode）438. 找到字符串中所有字母异位词 - 力扣（LeetCode）题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。

XY.散人

3196人浏览 · 2024-10-15 00:15:00

XY.散人 · 2024-10-15 00:15:00 发布

前言：

本文的主题是滑动窗口，通过两道题目讲解，一道是水果成篮，一道是找到字符串中的所有字母异位词。
链接分别为：
904. 水果成篮 - 力扣（LeetCode）

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。

水果成篮

题目解析

做这道题目不亚于做一道阅读理解，但是这道题本身就是属于高中的，题目又臭又长，但是题目要求确实很简单，所以根据题目描述，我们可以将题目总结为一句话，从一个数组里面选取两个数组成的最长子数组，就可以了，那么和之前做到最大的连续个数1基本上没有区别，所以暴力解法也就是一直遍历，确定起点，往后遍历到非A或B的数就可以了。此时的时间复杂度是标准的O(N^2)，那么代码编写就同学们下来自己实现咯。

算法原理

算法原理就非常简单了，需要一个变量判断种类，所以引入变量，又因为数的范围是10的五次方

所以引入的hash表为100001，并且是固定的三部曲，进窗口的时候维护kind，如果最开始为0，那么没有该水果种类，就可以直接kind++,++之后，就是判断，判断条件自然就是如果kind大于水果种类的话，就出窗口，就是自然的left++什么的咯，此时同时要维护kind，也就是如果哈希表的映射变为0了，那么kind就--，算法原理就这么多，没有特别要注意的。

算法编写

class Solution 
{
public:
    int totalFruit(vector<int>& fruits) 
    {
        int hash[100001] = { 0 };
        int ans = 0, kinds = 0;
        for(int left = 0,right = 0; right < fruits.size(); right++)
        {   
            //进窗口
            if(hash[fruits[right]]++ == 0) kinds++;
            //判断             
            while(kinds > 2)
            {
                if(--hash[fruits[left++]] == 0) kinds--;        
            }
            //更新结果
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

此时的时间复杂度是O(N)，运行的时间也是比较快的：

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

题目解析

题目要求的很简单，返回所有异位词的起始索引就可以了。

那么首先我们要搞清楚一个点，什么是异位词？

比如abc，异位词就是将abc进行排列组合之后组成的字符串，这就叫做异位词。那么我们判断某个字串是不是异位词难道是需要将所有的字符串进行比对吗？

高中的排列相信大家都是学习了，当然知道一个字符串排列之后的数字有多么庞大，所以我们不会一个一个比较，我们使用的第一种方法是使用哈希表映射，之后会对哈希表进行优化。

题目要求也是没有要特别注意的，现在就进入算法原理部分。

算法原理

算法一眼判定为滑动窗口，因为我们是用一个连续的区间，来和另一个连续的区间进行比较，那么正常的就是进窗口，出窗口，进行判断，进窗口自然是使用right指针，进窗口之后。

什么时候出窗口呢？

当然是right和left的区间的长度大于了目标字符串的长度，此时需要出窗口，左边出窗口即可。

但是有个难题是，如何判断区间的字符串是否目标字符串的异位词呢？

这里我们不妨使用哈希映射，统计目标字符串中字符出现的频次，第一个哈希表用来计算目标字符串出现的字母频次，第二个哈希表用来计算左右区间出现的字符频次，最后比较两个哈希表是否相等就可以了。

那么出窗口的时候，如果目标字符的频次变成了0，就肯定是要删除该元素的，所以需要erase，这里对容器使用不太熟练的同学自然需要看看文档。

此时那么出窗口之后，两个哈希表判断是否相等，相等更新结果就可以了。

这是使用哈希表解决。那么优化我们放在算法编写里面。

算法编写

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ans;
        unordered_map<char,int> hash1;//哈希表1
        unordered_map<char,int> hash2;//哈希表2
        for(auto e : p) hash1[e]++;//哈希表1判断p字符串的频次
        //滑动窗口
        for(int left = 0, right = 0; right < s.size(); right++)
        {
            //进窗口
            hash2[s[right]]++;
            //判断是否需要出窗口
            if((right - left + 1) > p.size())
            {
                //出窗口
                char out = s[left];
                if(--hash2[out] == 0) hash2.erase(out);
                left++;
            }
            //更新结果
            if(hash1 == hash2)
            ans.push_back(left);
        }
        return ans;
    }
};

当我们通过了之后，时间复杂度居然是有点高的，这里实际上是因为哈希表的删除增加是有点费时间的，我们进行hash[]++的时候，如果没有这个元素，哈希表会插入该元素，消耗的时间就有点高了。所以我们可以进行修改，使用数组模拟实现哈希表。

使用数组模拟哈希表，我们需要注意的点是：

第一，字母只有26个，并且都是小写的，所以我们第一个数组只需要开26个空间就可以了。

第二，更新结果之前的判断我们应该另外引入一个变量，因为没有函数能直接判断两个数组相等，所以我们引入变量的目的是用来计算有效字符的个数，因为对于异位词来说，有效字符的个数就是相当于排序之后的任意字符串的一个一致结果，所以可以使用Int变量统计即可。

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ans;
        int hash1[26];//哈希表1
        int hash2[26];//哈希表2
        int kinds = 0;//统计有效字符的个数
        for(auto e : p) hash1[e - 'a']++;//哈希表1判断p字符串的频次
        //滑动窗口
        for(int left = 0, right = 0; right < s.size(); right++)
        {
            //进窗口
            if(++hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])
            kinds++;
            //判断是否需要出窗口
            if(right - left + 1 > p.size())
            {
                //出窗口
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']) kinds--;
            }
            //更新结果
            if(kinds == p.size())
            ans.push_back(left);
        }
        return ans;
    }
};

第三就是下标要记得-'a'，并且进窗口需要维护kinds，出窗口仍然需要维护kinds，在后面有一道题也是，进窗口需要维护计数器，出窗口也需要维护计数器。

此时的运行时间就提起来了：