【优选算法】Sliding-Chakra：滑动窗口的算法流（下）

水果成篮

✏️题目描述：

✏️示例：

传送门：水果成篮

题解:

首先解读题意，简单来说就是找到一个区间，其中的果树种类用数字表示，种类不超过两种，题目默认是能找到至少两种水果，所以求在此前提下能找到的最长区间是多少？

💻第一步：

或许该题可以使用暴力解法解决，但明显时间复杂度太高无法通过示例
因此根据前些题目的经验，由于是找区间，而且要统计种类数量，滑动窗口＋哈希表

💻第二步：

具体的窗口滑动如图所示

先让第一个数据录入，即进窗口，判断不断循环，然后right依次向后移并不断往哈希表录入每个位置种类和更新数据，直到哈希表内的键值对大于2，即种类大于2；此时left减去第一个数据，即出窗口，判断不断循环，然后不断向后移直到哈希表里的一个种类数据变为0，对其进行erase操作减少一个种类，再次开始更新数据

💻代码实现:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    int totalFruit(vector<int>& fruits)
    {
        unordered_map<int, int> hash;
        int ret = 0, n = fruits.size();
        for (int left = 0, right = 0; right < n; ++right)
        {
            hash[fruits[right]]++;
            while (hash.size() > 2)
            {
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0)
                {
                    hash.erase(fruits[left]);
                }
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

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

✏️题目描述：

✏️示例：

传送门：找到字符串中所有字母异位词

题解:

首先我们要知道什么是异位词？

本题第一难为解读题意，通常读不懂题目时要多结合示例分析，结合示例1和示例2，把p这个字符串放在s这个字符串里比对，不考虑p的顺序，找到所有异位词，返回其起始下标

💻第一步：

先思考如何在代码运行过程中判断其是否为异位词，只判断个数显然是不行的，既要种类相同，又要出现的个数相同，因为哈希表会减慢运行，这里也只有26种字母，所以我们可以给需要找到的字符串创建模拟哈希表hash1，被寻找的字符串创建模拟哈希表hash2，对比两个哈希表的种类及数量就能准确得出是否为异位词

💻第二步：

具体实现的流程图如图所示，与前些写的题有些许不同

先让第一个数据录入，即进窗口，判断不断循环，然后right依次向后移并不断往哈希表中录入，直到left和right之间的长度大于字符串p；此时left减去第一个数据，即出窗口，判断不断循环，然后向后移1位使长度继续维持为字符串p，check然后如果符合要求则更新结果。然后right向前一位，判断，left向前一位，判断更新结果，以此循环

💻细节问题

这里重点在于如何更新结果，一般的思路是遍历hash1和hash2，并对比两个数组，显然此方法是冗余复杂的，接下来将介绍一种方法，通常想不到，因此很有学习价值

先统计字符串p中的字符种类及数量，count表示s中left和right之间的种类数量，在right移动过程中，字符串s的起始种类数量都为0，然后当字符串s的种类数量小于等于字符串p的种类数量时，说明该位置增加的是有效字符，count++

还是滑动窗口的起始操作，如图当right到e时，明显超出了字符串p的大小，left应该在c，移动left到b，然后当字符串s的种类数量小于等于字符串p的种类数量时，说明该位置减少的是有效字符，count--

最后当两个模拟哈希表中的种类数量相等，即count == m

💻代码实现:

#include <iostream>
#include <vector>
using namespace std;

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ret;
        int hash1[26] = { 0 };
        for (auto ch : p)
        {
            hash1[ch - 'a']++;
        }
        int hash2[26] = { 0 };
        int n = s.size();
        int m = p.size();
        for (int left = 0, right = 0, count = 0; right < n; ++right)
        {
            hash2[s[right] - 'a']++;
            if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])
            {
                count++;
            }
            if (right - left + 1 > m)
            {
                if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a'])
                {
                    count--;
                }
                hash2[s[left] - 'a']--;
                left++;
            }
            if (count == m)
            {
                ret.push_back(left);
            }
        }
        return ret;
    }
};

串联所有单词的子串

✏️题目描述：

✏️示例：

传送门：串联所有单词的子串

题解:

本题的题意也有些难以理解，但是结合找到字符串中所有字母异位词这题的铺垫，使得这题也不是无从下手

如图所示，把这些字符串看成一个个的字符，是不是就和之前那题是一样的？

💻细节问题

w每个字符串的长度多长，那么left，right就有几种起始情况

当right移动到最后不足字符串w的长度时，会发生越界，所以要写为right + len <= n

💻代码实现:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution 
{
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        unordered_map<string, int> hash1;
        for (auto s : words)
        {
            hash1[s]++;
        }
        vector<int> ret;
        int len = words[0].size(), m = words.size(), n = s.size();
        for (int i = 0; i < len; ++i)
        {
            unordered_map<string, int> hash2;
            for (int left = i, right = i, count = 0; right + len <= n; right += len)
            {
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in])
                {
                    count++;
                }
                if (right - left + 1 > len * m)
                {
                    string out = s.substr(left, len);
                    if (hash1.count(out) && hash2[out] <= hash1[out])
                    {
                        count--;
                    }
                    hash2[out]--;
                    left += len;
                }
                if (count == m)
                {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};

最小覆盖子串

✏️题目描述：

✏️示例：

传送门：最小覆盖子串

题解:

本题题意为在字符串s里找到一个含有t的字符串区间，只要该区间内符合t的种类数量即可，无论其他的字符有多少个

💻细节问题

所以本题虽说是困难难度，但是依据前几题的思路铺垫，这道题也能说不在话下了，依旧是模拟哈希表+滑动窗口（因为哈希表太占空间了，影响效率）

注意当是当hash2中的种类数量和hash1中的种类数量一样时才count++

💻代码实现:

#include <iostream>
#include <string>
using namespace std;

class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int hash1[128] = { 0 };
        int kinds = 0;
        for (auto ch : t)
        {
            if (hash1[ch]++ == 0)
            {
                kinds++;
            }
        }
        int hash2[128] = { 0 };
        int n = s.size(), minlen = INT_MAX, begin = -1;
        for (int left = 0, right = 0, count = 0; right < n; ++right)
        {
            if (++hash2[s[right]] == hash1[s[right]])
            {
                count++;
            }
            while (count == kinds)
            {
                if (right - left + 1 < minlen)
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                if (hash2[s[left]]-- == hash1[s[left]])
                {
                    count--;
                }
                left++;
            }
        }
        if (begin == -1)
        {
            return "";
        }
        else
        {
            return s.substr(begin, minlen);
        }
    }
};

也是第一次用时击败100%，比官方还优秀的解法😎

---

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！