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

【算法一周目】滑动窗口（2）

article 2024/11/27 9:10:36

水果成篮

解题思路

代码实现

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

解题思路

代码实现

串联所有单词的子串

解题思路

代码实现

最小覆盖子串

解题思路

代码实现

水果成篮

题目链接：904. 水果成篮

题目描述：
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。你想要尽可能多地收集水果，但是有一些规则：

你有两个篮子，每个篮子只能装一种类型的水果，篮子的容量无限制。
你可以选择任意一棵树开始采摘，但必须从这棵树开始依次向右采摘每棵树上的水果。
一旦遇到某棵树上的水果不符合篮子中的水果种类，你必须停止采摘。

返回你能采摘的最多的水果数量。

解题思路

解法：滑动窗口+哈希

根据题目要求，所求问题其实就是找一段最多只含两个不同元素的最长子区间，我们使用滑动窗口+哈希解决。

有一点值得注意，fruits[i] 是第 i 棵树上的水果种类，不是种类数。

具体过程如下：

1.初始化哈希表 hash，左右指针 left 和 right，记录结果的变量 ret。
2.right 向右遍历数组，将 right 位置的水果加入哈希表，统计频次。
如果哈希表的大小超过2，让left++并同时更新哈希表，直至哈希表的大小不超过2。
3.更新结果 ret。
4重复上述过程，直到 right 遍历完数组。

代码实现

1.使用unordered_map作为hash表

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 统计滑动窗口内水果的种类和数量
        unordered_map<int, int> hash;
        int n = fruits.size(), ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            //进窗口，将水果加入hash表
            hash[fruits[right]]++;

            //若水果种类超过2，收缩窗口直到种类不超过2
            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;
    }
};

2.使用数组模拟hash表

题目其实有提到 fruits[i] 的范围，所以我们不必真的使用unordered_map作为hash表，使用数组模拟即可，这样虽然会浪费空间，但是提高了效率。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100000] = { 0 };
        //cnt用于统计hash表的水果的种类个数
        int n = fruits.size(), ret = 0, cnt = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            hash[fruits[right]]++;
            if(hash[fruits[right]] == 1) cnt++;
            while(cnt > 2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left++]] == 0) cnt--;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

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

题目链接：438. 找到字符串中所有字母异位词

题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。顺序可以不考虑。

异位词是指由相同字母重排列形成的字符串（包括相同的字符串）。

解题思路

解法：滑动窗口 + 哈希

因为字符串 p 的异位词的长度一定于字符串 p 的长度相等，所以我们可以在字符串 s 中使用与字符串 p 等长度的滑动窗口来求解。

我们可以使用两个大小为26的数组来模拟哈希表，用于统计窗口内的字母频次和字符串s的字母频次，当比较得到两个哈希表相等时，说明滑动窗口中每种字母的数量与字符 p 每种字母的数量相同，窗口内的字符是字符 p 的一个异位词，此时记录窗口起始索引。

具体过程如下：

1.初始化 left 和 right 指针来维护滑动窗口，两个大小为26的数组 hash1 和 hash2 来模拟哈希表，记录字符串 p 的字母频次和窗口字母频次。

2.right 向右遍历数组
right 位置的字母入窗口，将其加入哈希表。
当滑动窗口长度大于字符串 p 的长度时，left++，将窗口左侧字母移除同时更新其在哈希表的频次。

3.更新结果，当 hash1 与 hash2 相等时，记录窗口起始索引。

注意：判断两个 hash 表是否相等的时间复杂度较高，效率较低。故我们要优化更新结果的判断条件（两个哈希表相等），我们可以来使用一个变量 cnt 记录窗口内的字母相较于字符串 p 的有效字符的数量，并在入窗口和窗口时维护 cnt，这样更新结果时，只需判断 cnt 是否等于字符串 p 的长度就可以知道窗口字符是否是字符串 p 的异位词。

解释下有效字符的数量，其实就是让窗口的组成字母尽可能接近字符 p ，当有效字符的数量等于字符 p 的长度，就说明了窗口的字母频次与字符 p 的字母频次相等，这也是比较两个统计字母频次的哈希表相等的本质，cnt 间接完成了这个任务。

代码实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int n = s.size(), m = p.size();
        //统计p字符串中每个字母出现的个数
        int hash1[26] = { 0 };
        for(auto ch : p) hash1[ch - 'a']++;
        
        //统计窗口中每个字母出现的个数
        int hash2[26] = { 0 };
        //统计窗口中有效字符的数量
        int cnt = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            //进窗口 + 维护cnt
            char in = s[right];
            hash2[in - 'a']++;
            if(hash2[in - 'a'] <= hash1[in - 'a']) cnt++;

            //窗口长度大于字符串p的长度，窗口左端字母出窗口，
            //并更新cnt和哈希表
            if(right - left + 1 > m)
            {
                char out = s[left++];
                //出窗口 + 维护cnt
                if(hash2[out - 'a'] <= hash1[out - 'a']) cnt--;
                hash2[out - 'a']--;
            }

            //更新结果
            if(cnt == m) ret.push_back(left);

        }
        return ret;
    }
};

时间复杂度：O(n)

空间复杂度：O(1)

串联所有单词的子串

题目链接：30. 串联所有单词的子串

题目描述：

给定一个字符串 s 和一个字符串数组 words，words 中所有字符串的长度相同。s 中的串联子串是指包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" 和 "efcdab" 都是串联子串，而 "acdbef" 不是串联子串，因为它不是 words 排列的连接。

返回所有串联子串在 s 中的开始索引，顺序可以不考虑。

解题思路

解法：滑动窗口 + 哈希表

这道题就是找到字符串中所有字母异位词的升级版，从原来处理单个字符变成了处理单个单词，我们只需要将 words 的单词看成单个字母就行了，然后用滑动窗口 + 哈希表解决。

具体过程：

1.用哈希表 hash1 记录 words 中每个单词的频次。

2.遍历字符串 s ，并用哈希表 hash2 来维护滑动窗口内的单词频次，注意每次增加窗口的大小为单词的长度。

3.当窗口大小大于所有单词的总长度时，出窗口和更新 hash2 。

4.当 hash1 和 hash2 两个哈希表相等时，更新结果。

判断两个哈希表是否相等消耗较大，用 count 来优化，count 统计滑动窗口内有效单词的个数。当 count 与 words 的单词个数相等时，说明找到了符合条件的一个窗口。

代码实现

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1;
        for(auto& e : words) hash1[e]++;

        int len = words[0].size(), m = words.size(), n = s.size();
        //执行len次滑动窗口
        for(int i = 0; i < len; ++i)
        {
            unordered_map<string, int> hash2;
            for(int left = i, right = i, count = 0; right <= n - len; right += len)
            {
                //进窗口+维护count
                string in(s.begin() + right, s.begin() + right + len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
                
                //判断+出窗口+维护count
                if(right - left + 1 > m * len)
                {
                    string out(s.begin() + left, s.begin() + left + len);
                    if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    left += len;
                }

                //更新结果
                if(count == m)
                    ret.push_back(left);
            }
        }

        return ret;
    }
};

1.执行 len 次滑动窗口（len 是单词长度）：由 s 字符串的长度不一定是单词长度的整数倍，需要执行 len 滑动窗口来保证答案的完整性。

2.注意 right 的范围，right 最后一次执行循环的位置应该是在 n - len 处。

时间复杂度：O( n * len)，其中 n 是字符串 s 的长度，需要 len 次滑动窗口，每次遍历一次 s。

空间复杂度：O(m * len)，m 是单词个数，每次滑动窗口都需要用一个哈希表来存储单词频次。

最小覆盖子串

题目链接：76. 最小覆盖子串

题目描述：

给你一个字符串 s 和一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在这样的子串，则返回空字符串 ""。

注意：

对于 t 中重复的字符，最小子串中该字符数量必须不少于 t 中的字符数量。
如果存在这样的子串，答案是唯一的。

解题思路

解法：滑动窗口+哈希

根据题目，我们直接根据暴力解法来优化，就得到滑动窗口+哈希的解题方法。

具体过程如下：

1.利哈希表 hash1 来统计字符串 t 中每个字符出现的频次。

2.使用滑动窗口遍历字符串 s ，并用哈希表 hash2 来统计窗口中字符频次。

3.当窗口的字符频次满足要求时，更新结果，然后收缩窗口，直到窗口字符频次不满足要求。

注意：这里判断窗口的字符频次满足要求不是判断两个哈希表是否相等，而是 hash1 的字符频次要完整的出现在 hash2 中，hash1 中可以出现除字符串 t 中的字符以外的字符频次。也就是说，窗口内只要完整出现字符串 t 的所有字符即可（字符种类及其对应的频次）。

我们这里还是利用 count 来完成判断，这里的 count 统计的时有效字符的种类，只有 t 中的单个字符在窗口内出现的频次与在 t 中完全一样，count 才自增1，同理，频次不相等时就自减 1，当 count 与 t 中字符种类数相同时，说明找到一个符合条件的覆盖字串，更新结果。

代码实现

class Solution {
public:
    string minWindow(string s, string t) {
        string ret;

        //hash1统计t字符频次和计算hash1的大小，hash1size统计t的字符种类
        int hash1[128] = { 0 }, hash1size = 0;
        for(auto e : t) 
            if(hash1[e]++ == 0) hash1size++;

        //hash2统计窗口字符频次
        int hash2[128] = { 0 };
        int len = INT_MAX, start = 0;
        //count统计有效字符的种类
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            //进窗口 + 维护count
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;
            //判断
            while(count == hash1size)
            {
                //更新结果
                if(right - left + 1 < len)
                {
                    len = right - left + 1;
                    start = left;
                }
                
                //出窗口+维护count
                char out = s[left++];
                if(hash2[out]-- == hash1[out]) count--;
            }
        }
        ret = len == INT_MAX ? "" : s.substr(start, len);
        return ret;
    }
};

时间复杂度：O(n)

空间复杂度：O(1)

拜拜，下期再见😏

摸鱼ing😴✨🎞