Hoshiᅟᅠ     

Hoshiᅟᅠ     

C++ 滑动窗口详解:进阶题解与思维分析


前言


第二章:进阶挑战

2.1 水果成篮

题目链接904. 水果成篮

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

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

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

示例 1

  • 输入:fruits = [1,2,1]
  • 输出:3
  • 解释:你可以采摘所有 3 棵树上的水果。

示例 2

  • 输入:fruits = [0,1,2,2]
  • 输出:3
  • 解释:你只能采摘 [1,2,2] 这三棵树的水果。如果从第 1 棵树开始采摘,只能采摘到 [0,1]。

示例 3

  • 输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
  • 输出:5
  • 解释:你可以采摘 [1,2,1,1,2] 这五棵树的水果。

提示:

  • 1 <= fruits.length <= 105
  • 0 <= fruits[i] < fruits.length

解法一:滑动窗口

算法思路

具体步骤:

  1. 用一个哈希表 hash 记录滑动窗口内的水果种类和数量。
  2. 滑动窗口的右边界 right 向右移动,每次将新水果加入哈希表。
  3. 如果哈希表中记录的水果种类超过两个,左边界 left 开始向右移动,直到窗口内水果种类不超过两个为止。
  4. 在每次满足条件时,更新最大收集到的水果数量 ret

算法流程

  1. 初始化哈希表 hash,左右指针 leftright,以及记录结果的变量 ret
  2. 遍历数组 fruits,对每个水果进行如下操作:
    • right 指向的水果加入哈希表,统计频次。
    • 如果哈希表的大小超过 2,左指针 left 向右移动,同时更新哈希表,直到哈希表中只有两种水果。
    • 在满足条件时,更新最大采摘数量 ret
  3. 返回结果。

代码实现

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

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> hash; // 统计滑动窗口内水果的种类和数量
        int ret = 0; // 记录最大水果数量
        int left = 0; // 左指针
        
        for (int right = 0; right < fruits.size(); ++right) {
            hash[fruits[right]]++; // 右指针扩展窗口,加入新水果
            
            // 如果种类超过 2,收缩窗口
            while (hash.size() > 2) {
                hash[fruits[left]]--; // 移除左边水果
                if (hash[fruits[left]] == 0) {
                    hash.erase(fruits[left]); // 种类为 0,删除该水果
                }
                left++; // 左指针向右移动
            }
            
            ret = max(ret, right - left + 1); // 更新最大水果数量
        }
        
        return ret;
    }
};

解法二:滑动窗口 + 数组模拟哈希表

算法思路

代码实现

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = {0};  // 数组模拟哈希表
        int ret = 0;             // 记录结果
        int left = 0;            // 左指针
        int kinds = 0;           // 记录当前窗口内的水果种类数
        
        for (int right = 0; right < fruits.size(); ++right) {
            if (hash[fruits[right]] == 0) kinds++;  // 新种类水果进入窗口
            hash[fruits[right]]++;  // 统计数量
            
            // 当水果种类超过 2 时,收缩窗口
            while (kinds > 2) {
                hash[fruits[left]]--;  // 移除左边水果
                if (hash[fruits[left]] == 0) kinds--;  // 种类数量减少
                left++;  // 左指针右移
            }
            
            ret = max(ret, right - left + 1);  // 更新最大水果数量
        }
        
        return ret;
    }
};

复杂度分析:
  • 时间复杂度O(n),每个元素最多被左右指针访问两次。
  • 空间复杂度O(n),哈希表或数组最多存储 n 种水果的频次。

图解分析:
示例:
  • 输入fruits = [3,3,3,1,2,1,1,2,3,3,4]
  • 输出5
  • 解释:你可以采摘 [1,2,1,1,2] 这五棵树的水果。

滑动窗口执行过程图解:

详细说明:
  1. Iteration 1-3Right 扩展到 2,窗口内只有一种水果 3,因此子数组为 [3,3,3],长度为 3
  2. Iteration 4:加入水果 1,种类增加到两种,窗口变为 [3,3,3,1],长度更新为 4
  3. Iteration 5:加入水果 2,种类增加到三种,此时需要调整窗口,移动 Left,直到只剩两种水果。经过调整,窗口变为 [1,2,1]
  4. Iteration 6-8:继续右移 Right,窗口内的水果种类保持为两种,最大长度更新为 5,子数组为 [1,2,1,1,2]
  5. Iteration 9-11:加入水果 3,水果种类再次超出限制,继续收缩窗口,最终找到的最大子数组长度为 5

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

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

题目描述

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

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

示例 1

  • 输入:s = "cbaebabacd", p = "abc"
  • 输出:[0,6]
  • 解释:
    起始索引为 0 的子串是 "cba",它是 "abc" 的异位词。
    起始索引为 6 的子串是 "bac",它是 "abc" 的异位词。

示例 2

  • 输入:s = "abab", p = "ab"
  • 输出:[0,1,2]
  • 解释:
    起始索引为 0 的子串是 "ab",它是 "ab" 的异位词。
    起始索引为 1 的子串是 "ba",它是 "ab" 的异位词。
    起始索引为 2 的子串是 "ab",它是 "ab" 的异位词。

提示

  • 1 <= s.length, p.length <= 3 * 10^4
  • sp 仅包含小写字母。

解法:滑动窗口 + 哈希表

算法思路

  1. 窗口大小固定
    因为异位词的长度一定与字符串 p 的长度相同,所以我们构造一个长度为 p.size() 的滑动窗口,每次右移窗口,动态维护窗口内每个字母的出现频次。

  2. 频次匹配判断
    通过两个大小为 26 的数组来统计字母出现的次数,分别用于存储当前窗口内字母频次(hash2)和 p 中的字母频次(hash1)。当两个数组的内容相同,说明当前窗口就是 p 的一个异位词。

  3. 窗口移动
    每次右移窗口时,更新窗口内字母的频次。如果窗口超过 p.size(),需要将最左边的字母移出窗口。若在滑动过程中,两个数组的内容始终保持一致,那么我们记录该窗口的起始索引。


算法流程

  1. 初始化两个大小为 26 的数组 hash1hash2,分别记录 p 中字母的频次和窗口中字母的频次。
  2. 遍历字符串 s,使用右指针 right 逐渐扩大窗口:
    • 每次将窗口右端的字母加入窗口,并更新其频次。
    • 若窗口超过 p.size(),则需要从左侧移出一个字母,并更新频次。
  3. hash1hash2 相等时,说明当前窗口是 p 的一个异位词,记录其起始位置。
  4. 最后返回所有满足条件的起始位置列表。

代码实现

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
        for(auto ch : p) hash1[ch - 'a']++; 
        
        int hash2[26] = { 0 }; // 统计窗口里面的每一个字符出现的个数
        int m = p.size();
        
        for(int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            // 进窗口 + 维护 count
            if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            
            if(right - left + 1 > m) {  // 判断窗口是否需要收缩
                char out = s[left++];
                // 出窗口 + 维护 count
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            
            // 更新结果
            if(count == m) ret.push_back(left);
        }
        
        return ret;
    }
};

复杂度分析:
  • 时间复杂度O(n),每个字符最多被左右指针访问两次,因此时间复杂度为线性。
  • 空间复杂度O(1),只需要常数级别的额外空间用于存储两个固定大小的数组。

图解分析:

假设输入为 s = "cbaebabacd", p = "abc",通过滑动窗口的执行过程如下:

滑动窗口执行过程图解:

详细说明:
  1. Iteration 1-3Right=0Right=2,窗口内包含 [c, b, a],它与 p="abc" 完全匹配,属于异位词,记录起始索引 0

  2. Iteration 4Right=3,窗口内包含 [b, a, e],字母 e 不在 p 中,因此当前窗口不是异位词。

  3. Iteration 5Right=4,窗口内包含 [a, e, b],依旧不匹配 p,当前窗口不是异位词。

  4. Iteration 6Right=5,窗口内包含 [e, b, a],仍然不匹配 p,当前窗口不是异位词。

  5. Iteration 7Right=6,窗口内包含 [b, a, d]d 不在 p 中,因此当前窗口不是异位词。

  6. Iteration 8Right=7,窗口内包含 [a, b, a],当前窗口不是异位词。

  7. Iteration 9Right=8,窗口内包含 [b, a, c],这再次是 p="abc" 的排列,属于异位词,记录起始索引 6

  8. Iteration 10Right=9,窗口内包含 [a, c, d]d 不在 p 中,因此当前窗口不是异位词。


2.3 串联所有单词的子串

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

题目描述

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

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

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

示例 1

  • 输入:s = "barfoothefoobarman", words = ["foo","bar"]
  • 输出:[0,9]
  • 解释:
    子串 "barfoo" 的起始索引为 0,它是 words 中按顺序排列的连接。
    子串 "foobar" 的起始索引为 9,它是 words 中按顺序排列的连接。

示例 2

  • 输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
  • 输出:[]
  • 解释:
    字符串中没有符合要求的串联子串。

示例 3

  • 输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
  • 输出:[6,9,12]
  • 解释:
    子串 "foobarthe" 的起始索引为 6,它是 words 中按顺序排列的连接。
    子串 "barthefoo" 的起始索引为 9,子串 "thefoobar" 的起始索引为 12

提示

  • 1 <= s.length <= 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i]s 仅包含小写英文字母。

解法:滑动窗口+哈希表

算法思路

【优选算法篇】踏入算法的深邃乐章:滑动窗口的极致探秘-LMLPHP

具体步骤:

  1. 使用哈希表 hash1 记录 words 中每个单词的频次。
  2. 遍历字符串 s,每次滑动窗口的大小为 words 中单词的总长度。
  3. 在每个窗口内,维护另一个哈希表 hash2,用于记录当前窗口内单词的频次。
  4. 当两个哈希表的内容一致时,说明当前窗口是一个符合要求的串联子串,记录其起始索引。

算法流程

  1. 初始化 hash1,用于存储 words 中单词的频次。
  2. 遍历 s,通过滑动窗口按单词长度为步长,维护窗口内单词的频次。
  3. 当窗口内的单词频次与 words 中的单词频次一致时,记录该窗口的起始索引。

代码实现

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

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1;  // 保存 words 中所有单词的频次
        for (auto& word : words) hash1[word]++;
        
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) {  // 执行 len 次
            unordered_map<string, int> hash2;  // 维护窗口内单词的频次
            for (int left = i, right = i, count = 0; right + len <= s.size(); 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;
    }
};

复杂度分析:
  • 时间复杂度O(n * m * l),其中 n 是字符串 s 的长度,mwords 中单词的个数,l 是单词的长度。每个单词被扫描一次,并且最多执行 len 次完整的窗口扫描。
  • 空间复杂度O(m * l),用于存储 words 中单词的哈希表以及滑动窗口中的哈希表。

图解分析:
滑动窗口执行过程图解:

假设输入为 s = "barfoothefoobarman", words = ["foo", "bar"],通过滑动窗口的执行过程如下:


详细说明:
  1. Iteration 1:窗口内的单词为 [bar],不构成完整的串联子串。
  2. Iteration 2:窗口扩大,内含 [bar, foo],它是 words 中单词的排列,记录起始索引 0
  3. Iteration 3:窗口滑动,内含 [foo, bar],它是 words 中单词的排列,记录起始索引 9

2.4 最小覆盖子串

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

题目描述

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

注意:

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

示例 1

  • 输入:s = "ADOBECODEBANC", t = "ABC"
  • 输出:"BANC"
  • 解释:最小覆盖子串 "BANC" 包含字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2

  • 输入:s = "a", t = "a"
  • 输出:"a"
  • 解释:整个字符串 s 就是最小覆盖子串。

示例 3

  • 输入:s = "a", t = "aa"
  • 输出:""
  • 解释:t 中两个字符 ‘a’ 应该都出现在子串中,而 s 中只有一个 ‘a’,因此不存在符合条件的子串。

提示

  • 1 <= s.length, t.length <= 10^4
  • st 由英文字母组成。

解法:滑动窗口 + 哈希表

算法思路


算法流程

  1. 初始化两个哈希表,hash1 用来记录 t 中每个字符的频次,hash2 用来记录窗口内的字符频次。
  2. 使用滑动窗口,右指针 right 不断向右扩展窗口,同时更新窗口内的字符频次。
  3. 每当窗口内的字符频次满足 t 中的要求,开始收缩左指针 left,缩小窗口并更新最小子串的长度。
  4. 当遍历结束后,返回最小子串的起始索引和长度。

代码实现

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

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 }; // 记录字符串 t 中每个字符的频次
        int kinds = 0;          // 统计 t 中不同的字符种类
        for (auto ch : t) {
            if (hash1[ch]++ == 0) kinds++;
        }

        int hash2[128] = { 0 }; // 记录窗口中每个字符的频次
        int minlen = INT_MAX, begin = -1; // 初始化最小长度和起始位置
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++;  // 进窗口 + 维护 count
            
            // 如果当前窗口满足条件,尝试收缩窗口
            while (count == kinds) {
                if (right - left + 1 < minlen) {    // 更新最小长度和起始位置
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];               // 收缩窗口
                if (hash2[out]-- == hash1[out]) count--;  // 出窗口 + 维护 count
            }
        }

        // 返回结果
        if (begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};

复杂度分析:
  • 时间复杂度O(n),其中 n 是字符串 s 的长度,滑动窗口遍历每个字符最多两次。
  • 空间复杂度O(1),哈希表的大小固定为 128,存储字符频次。

图解分析:

假设输入为 s = "ADOBECODEBANC", t = "ABC",滑动窗口的执行过程如下:

滑动窗口执行过程图解:

详细说明:
  1. Iteration 1-5:滑动窗口从 Left=0 开始向右扩展,但字符尚未覆盖 t="ABC" 的所有字符,因此没有有效窗口。
  2. Iteration 6Right=5 时,窗口内字符为 [A, D, O, B, E, C],此时首次找到覆盖 t 的有效窗口,记录最小子串为 "ADOBEC"
  3. Iteration 7-10:随着窗口向右扩展,字符无法继续满足 t 的要求,最小子串保持为 "ADOBEC"
  4. Iteration 11Right=10 时,窗口内字符为 [D, O, B, E, C, O, D, E, B, A],再次满足条件,最小子串仍保持为 "ADOBEC"
  5. Iteration 12:窗口左移到 Left=5,依然保持有效窗口,字符为 [C, O, D, E, B, A],最小子串保持不变。
  6. Iteration 16Right=12 时,窗口内字符为 [B, A, N, C],再次找到有效窗口,更新最小子串为 "BANC"

写在最后


以上就是关于【优选算法篇】踏入算法的深邃乐章:滑动窗口的极致探秘的内容啦,各位大佬有什么问题欢迎在评论区指正,或者私信我也是可以的啦,您的支持是我创作的最大动力!❤️

【优选算法篇】踏入算法的深邃乐章:滑动窗口的极致探秘-LMLPHP

10-19 20:50