解锁高效算法思维：滑动窗口法，让你轻松搞定复杂题！（3）

解锁高效算法思维：滑动窗口法，让你轻松搞定复杂题！（3）

前言：

在算法学习的旅程中，很多同学会被复杂的题目绊住脚步，尤其是当问题涉及到大量数据处理和优化时，往往会让人望而却步。而滑动窗口法，作为一种高效的算法思想，正是破解这类题目的一把利器。通过滑动窗口，我们可以在不增加时间复杂度的情况下动态调整解题范围，从而大幅提升解题效率。本文将带你深入理解滑动窗口的核心思想，通过丰富的例题和详细的讲解，助你轻松驾驭这项高效的算法技巧！

希望你在阅读本篇文章后，对滑动窗口法有更深的认识，也能够在遇到相关题目时更加得心应手。让我们一起解锁高效算法思维，挑战更高难度的题目吧！下面进入我们的代码时间。

正文：

1.水果成篮

1.1.题目来源

本题源自于力扣，下面放上链接：https://leetcode.cn/problems/fruit-into-baskets/

1.2.题目解析

本题目很长，有些读者朋友可能就在读题目讲解的时候就漏了怯，其实这个题目如果我们认真读起来的话，其实难度不算很大，下面小编就给各位简单的概括一下本题目：这个题目其实就是给了我们一个数组（数组的元素表示数的类型），我们需要找到一个子数组，使数组里面的类型小于等于2，找到符合条件的最长数组即可，这其实就是题目概括下来的内容，其实这个题目看起来，是很容易想到滑动窗口的解法的，通过给我们的第二个规矩即可看出：

右移就暗指我们需要使用滑动窗口或者暴力解法来做和这个题目，下面给出这个题目的思路解读。

1.3.题目思路解答

1.3.1.滑动窗口 + 哈希表

正如标题所言，此时这个题目我们还是需要用到一个数据结构——哈希表，因为哈希表可以存储元素的种类和个数，本题我们就是要记录水果的种类和个数，所以此时哈希表正好可以解决这个问题，所以我们在设立好一个哈希表以后，就可以设置两个指针来准备滑动窗口式遍历数组，首先我们就要先入窗口，入窗口的操作就是我们把元素存入哈希表中，之后我们就要进行判断，如果哈希表里面的元素个数大于2的话，此时我们就没有"篮子"装水果了，此时我们就需要进行出窗口操作，即让让左边位于哈希表中的元素减1，然后我们判断一下此时左边元素的个数是否为0，如果是0的话，那么此时我们就可以直接把这个元素删除，然后让左窗口往右边滑即可；否则我们就需要循环删除，直到哈希表内的元素种类小于等于2，之后我们就要进行更新数据的操作，此时我们记录数组的长度，并且和之前的数做比较，保留最大的那个，然后right指针往右遍历即可，这就是这个题目的解法，下面小编进入代码实操部分。

1.4.代码实操

首先，我们需要准备好几个“工具”，一个是哈希表，这个哈希表是要用unordered_map表示（这个目前小编还没有学到，不知道的读者朋友我在这里简单说一下它的用法，它可以储存元素的种类和个数），还要有双指针（left和right），一个计数器（记录此时符合要求的数组的长度），下面给出代码：

unordered_map<int, int> hash;
int left = 0,right = 0,n = fruits.size(),ret = 0;

之后，我们就要进入循环，循环条件都是一样的（当然这不是肯定句，我害怕之后刷题我来打我自己的脸o(╥﹏╥)o），如下所示：

while(right < n)
{}

然后我们在循环体内就要进行那几个操作了，首先是入窗口操作：让哈希表存储right位置的元素，并且还有个数加1；然后我们进入判断条件，此时判断我们还是用循环完成，因为我们不能保证一次就能出窗口成功，此时的判断条件就是哈希表中的类型大于1，这里我们需要用到一个size()接口，这个接口代表着哈希表里面存储的元素，之后在这个循环体内，我们先要让left位置的元素个数-1，然后判断left位置的元素类型的个数是否已经到0了，如果到0，我们调用erase接口直接删除该元素即可，然后让left往后走，如果没找到，我们就继续循环，直到哈希表中的元素种类小于等于2即可，然后我们判断结束后就更新数据，此时我们调用max函数让此时的窗口的长度和计数器进行比较，大的是新计数器，下面小编给出这部分代码：

hash[fruits[right]]++;
while(hash.size() > 2)
{
    hash[fruits[left]]--;//控制个数的
    if(hash[fruits[left]] == 0) //当个数为0的时候，类型自然是要直接删掉的
    hash.erase(fruits[left]);
    left++;
}
ret = max(ret,right - left + 1);
right++;

之后我们直接返回长度即可，下面小编给出完整代码。

1.5.代码展示

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
            unordered_map<int, int> hash;
            int left = 0,right = 0,n = fruits.size(),ret = 0;
        while(right < n)
        {
            hash[fruits[right]]++;
            while(hash.size() > 2)
            {
                hash[fruits[left]]--;//控制个数的
                if(hash[fruits[left]] == 0) //当个数为0的时候，类型自然是要直接删掉的
                hash.erase(fruits[left]);
                left++;
            }
            ret = max(ret,right - left + 1);
            right++;
        }
        return ret;
    }
};

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

2.1.题目来源

本题依旧来自于力扣，下面小编给出链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/

2.2.题目解析

首先小编先说说异位词的意思：字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次

简单来说，就以示例一给我们的例子为例，此时我们s字符串的前三个字符，可以发现此时的cba虽然和p字符串的顺序不一样，但其实它就是属于一个异位词，异位词简单来说就是给定一个字符串（p），如果给定我们一个字符串（m），这个字符串每一个字符和p每一个字符虽然位置不一定一样，但是字符出现的次数是一样的话，那么就可以说明m是p的一个异位词，本题就是让我们在给定的字符串中找到p的异位词，并记录这个异位词的位置，遍历一遍数组，找到所有的位置，然后把这个位置的数据返回即可，这就是本题目的含义，下面小编给出思路讲解。

2.3.题目思路讲解

2.3.1.滑动窗口+哈希表

本题因为要统计数组中的元素个数，所以我们还是需要一个哈希表来存储数组的元素个数，并且还要准备两个哈希表，一个哈希表是为了记录p中对应位置的元素个数，一个哈希表是为了统计s中元素的个数，并且我们在s字符串找到的子串要保证和p字符串的元素个数一样，不然根本不可能是p字符串的异位词，所以其实这个限制条件就为我们之后的判断环节打下了基础，此时我们这个题目完全可以采取滑动窗口的方法来进行，因为可以这么想：我们反正都是要从数组开头进行遍历数组，并且还需要两个指针，一个指针是代表着左区间，一个指针代表着右区间，这不就正好是滑动窗口吗？所以此时我们通过滑动窗口就可以解决问题。下面我给出如何用滑动窗口来解决这个题目。

首先是入窗口的操作，此时我们在入窗口的时候就是让哈希表存储相应位置的元素以及个数，判断的条件我前面说了，如果此时的滑动窗口的长度大于了p字符串的长度，那这样指定是没有结果的，直接进行出窗口操作就好，并且此时我们也无须使用循环了，因为此时我们要保证数组的长度和p是一样的，当出了一次窗了，那么二者的长度就是一样的，这里我们在循环就没意义了，所以在判断完后，我们还要判断一下此时两个哈希表是否是一样的（这里需要额外写一个函数进行判断），如果相等，更新数据即可，即保存这个位置的数据，之后让right往右走即可，此时这就是这个题目的解析，下面小编进入代码实操部分。

2.4.代码实操

首先，我们需要书写两个函数，用来判断哈希表是相等的，此时我们仅需遍历一遍两个哈希表就好，如果对应位置元素个数相等，那么就证明此时的哈希表是相等的，由于难度不大，小编直接给出代码了。

bool check(int* hash1, int* hash2) {
    for(int i = 0; i < 26; ++i) {
        if(hash1[i] != hash2[i]) {
            return false;
        }
    }
    return true;
}

之后就进入主函数部分了，我们需要定义多个工具用来进行滑动窗口操作，此时我们需要准备两个哈希表，此时的哈希表的长度我们根据上述题目的提示，我们知晓此时的数组都是小写字母，所以我们定义一个26个长度的哈希表即可（我们等会在插入元素的时候别往减去-‘a’，用来保证此时的小写字母都在这个区间里），之后定义两个指针用来遍历数组，还需要俩遍历记录两个字符串的长度，一个vector容器保存出现异位词位置的数据，然后我们遍历一遍p字符串，把数据存入到其中一个哈希表里面，代码如下所示：

int hash1[26] = {0}; //用哈希表统计类型和种类，这是原数组的 
int hash2[26] = {0};
for(auto e : p)
{
    hash2[e - 'a']++;
}
int left = 0,right = 0,n1 = s.size(),n2 = p.size();
vector<int> s1;

之后我们就要进入循环，循环的条件自然是right不超过s字符串的长度即可。

while(right < n1)
{}

进入循环体里，我们根据那几部操作，先进行入窗口操作，此时就是把right位置的字符存入哈希表即可，之后我们就要进入判断条件，判断条件也很多容易，当此时的窗口长度大于第二个字符串的时候，我们就要进行入窗口操作，先把left位置的数据移除哈希表，然后让左窗口往右移动即可，此时的判断我们通过if语句即可，因为此时我们判断完后的数组长度就已经和第二个字符相同了，我们无须在进行出窗口了，之后我们通过check函数判断此时的两个哈希表是否相等，相等的话直接调用s1的push_back接口保存数据即可，之后我们让right往右走就好，到了这里我们就实现了循环体内代码书写。

hash1[s[right] - 'a']++;
if(right - left + 1 > n2)
{
    hash1[s[left++] - 'a']--;
}
if(check(hash1,hash2))
s1.push_back(left);
right++;

之后我们返回s1即可，下面小编给出完整代码。

2.5.代码展示

class Solution {
public:
    bool check(int* hash1, int* hash2) {
        for(int i = 0; i < 26; ++i) {
            if(hash1[i] != hash2[i]) {
                return false;
            }
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = {0}; //用哈希表统计类型和种类，这是原数组的 
        int hash2[26] = {0};
        for(auto e : p)
        {
            hash2[e - 'a']++;
        }
        int left = 0,right = 0,n1 = s.size(),n2 = p.size();
        vector<int> s1;
        while(right < n1)
        {
            hash1[s[right] - 'a']++;
            if(right - left + 1 > n2)
            {
                hash1[s[left++] - 'a']--;
            }
            if(check(hash1,hash2))
            s1.push_back(left);
            right++;
        }
        return s1;
    }
};

3.题目二的小优化

3.1.为何要优化？

此时我们难免会发现，上面的代码似乎有点太长了，我们不仅需要写主函数，还需要写一个check函数一个一个的判断两个哈希表是否相等，这样的话这个题目的复杂度难免会有点高，虽然上述的代码完全可以通过力扣的所有例子的，但是仅仅是因为这个题目的限制条件是有点多的，所以此时我们可以通过，所以我们需要像一个更好的解法来帮助我们优化这个算法。

3.2.如何去优化？

此时我们优化的点就是判断条件，此时这个check函数是有点耗费运行时间的，所以我们最好把这个点优化了，下面小编不卖关子了，给出一个优化方法：通过计数来避免check函数的使用，关于我们如何通过计数来实现，且听我细细道来。

首先我们要在上面的代码基础上，增加一个count变量，当我们在进行入窗口操作结束的时候，先写一个判断语句，倘若此时的hash1在right位置的数据小于等于hash2，说明此时我们在hash1存入了hash2中的元素【此时位置的元素正好是p字符串的字符】，此时我们就让count进行加1，在之后我们正常的判断语句中，再写入一个判断函数，判断此时我们在出窗口之前，left位置的数据hash1的个数是否小于等于hash2，如果符合条件，此时我们让count–，证明此时我们减少了一个属于p字符串的字符，更新结果的时候我们无须用check函数，仅需判断此时的count是否等于p字符串的长度，如果相等，证明此时的子串正好就是异位词，我们再往s1插入开始位置即可，此时我们就完成了优化，这里我们巧妙的统计两个哈希表对应位置的数据是否相等，通过count计数来实现了对于check函数的舍弃，实在是妙哉，下面小编给出优化后的代码。

3.3.优化后的代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = {0}; //用哈希表统计类型和种类，这是原数组的 
        int hash2[26] = {0};
        for(auto e : p)
        {
            hash2[e - 'a']++;
        }
        int left = 0,right = 0,n1 = s.size(),n2 = p.size(),count = 0;
        vector<int> s1;
        while(right < n1)
        {
            hash1[s[right] - 'a']++;
            if(hash1[s[right] - 'a'] <= hash2[s[right] - 'a'])
            count++;
            if(right - left + 1 > n2)
            {
            if(hash1[s[left] - 'a'] <= hash2[s[left] - 'a'])
            count--;
            hash1[s[left] - 'a']--;
            left++;
            }
            if(count == n2)
            s1.push_back(left);
            right++;
        }
        return s1;
    }
};

4.总结

今天同样是两个算法题的解析，小编认为这两个题还是蛮有教育意义的，各位读者朋友一定要熟悉它的用法，特别是第二个的优化，小编认为还是很妙的，如果文章有错误，请在评论区指出，我会及时纠正自己的错误，一起做题的时光总是很短暂的，那么各位大佬们，我们下一篇文章见啦！