💬 欢迎讨论:如有疑问或见解,欢迎在评论区留言互动。 👍 点赞、收藏与分享:如觉得这篇文章对您有帮助,请点赞、收藏并分享! 🚀 分享给更多人:欢迎分享给更多对 C++ 感兴趣的朋友,一起学习滑动窗口的基础与进阶!
在算法的世界中,滑动窗口是一种极具优雅和灵活性的算法技巧。在上一章中,我们通过几个经典问题初步领略了滑动窗口的强大之处。然而,算法的探索并没有止步于此。随着问题的复杂性逐渐提升,滑动窗口的应用场景也变得更加丰富多样。在这篇博客中,我们将继续深入探讨滑动窗口的进阶应用。通过更加灵活的策略、动态调整窗口,我们将解决一系列复杂的算法挑战,进一步揭示滑动窗口的无限可能。
接下来,让我们步入滑动窗口的进阶领域,探索更多算法之美。
题目链接:904. 水果成篮
题目描述:
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits
表示,其中 fruits[i]
是第 i
棵树上的水果种类。你想要尽可能多地收集水果,但是有一些规则:
返回你能采摘的最多的水果数量。
示例 1:
fruits = [1,2,1]
3
示例 2:
fruits = [0,1,2,2]
3
示例 3:
fruits = [3,3,3,1,2,1,1,2,3,3,4]
5
提示:
1 <= fruits.length <= 105
0 <= fruits[i] < fruits.length
算法思路:
本题是典型的滑动窗口问题。要求我们找到一个连续区间,其中只能有两种不同种类的水果(即至多两个不同元素)。通过滑动窗口,我们可以动态调整区间大小,保持窗口内水果种类不超过两种。
具体步骤:
hash
记录滑动窗口内的水果种类和数量。right
向右移动,每次将新水果加入哈希表。left
开始向右移动,直到窗口内水果种类不超过两个为止。ret
。算法流程:
hash
,左右指针 left
和 right
,以及记录结果的变量 ret
。fruits
,对每个水果进行如下操作: right
指向的水果加入哈希表,统计频次。left
向右移动,同时更新哈希表,直到哈希表中只有两种水果。ret
。代码实现:
#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;
}
};
算法思路:
利用数组
hash
来代替哈希表,用水果种类的值直接作为数组下标,来统计每种水果的数量。这种方式效率更高,因为直接使用数组的下标访问比哈希表操作更快。
代码实现:
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]
这五棵树的水果。Iteration | Left | Right | 水果种类 | 窗口内水果 | 窗口大小 | 最大结果 |
---|---|---|---|---|---|---|
1 | 0 | 0 | 1 | [3] | 1 | 1 |
2 | 0 | 1 | 1 | [3, 3] | 2 | 2 |
3 | 0 | 2 | 1 | [3, 3, 3] | 3 | 3 |
4 | 0 | 3 | 2 | [3, 3, 3, 1] | 4 | 4 |
5 | 0 | 4 | 3 | [3, 3, 3, 1, 2] | 5 | 5 |
6 | 3 | 5 | 2 | [1, 2, 1] | 3 | 5 |
7 | 3 | 6 | 2 | [1, 2, 1, 1] | 4 | 5 |
8 | 3 | 7 | 2 | [1, 2, 1, 1, 2] | 5 | 5 |
9 | 7 | 8 | 2 | [2, 3] | 2 | 5 |
10 | 7 | 9 | 2 | [2, 3, 3] | 3 | 5 |
11 | 8 | 10 | 2 | [3, 3, 4] | 3 | 5 |
Right
扩展到 2
,窗口内只有一种水果 3
,因此子数组为 [3,3,3]
,长度为 3
。1
,种类增加到两种,窗口变为 [3,3,3,1]
,长度更新为 4
。2
,种类增加到三种,此时需要调整窗口,移动 Left
,直到只剩两种水果。经过调整,窗口变为 [1,2,1]
。Right
,窗口内的水果种类保持为两种,最大长度更新为 5
,子数组为 [1,2,1,1,2]
。3
,水果种类再次超出限制,继续收缩窗口,最终找到的最大子数组长度为 5
。题目链接:438. 找到字符串中所有字母异位词
题目描述:
给定两个字符串 s
和 p
,找到 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
s
和 p
仅包含小写字母。算法思路:
这道题要求我们在字符串
s
中找到所有与字符串p
的 异位词 对应的子串。由于异位词由相同字母组成且长度与p
相同,因此我们可以使用滑动窗口来解决这一问题。
p
的长度相同,所以我们构造一个长度为 p.size()
的滑动窗口,每次右移窗口,动态维护窗口内每个字母的出现频次。
hash2
)和 p
中的字母频次(hash1
)。当两个数组的内容相同,说明当前窗口就是 p
的一个异位词。
p.size()
,需要将最左边的字母移出窗口。若在滑动过程中,两个数组的内容始终保持一致,那么我们记录该窗口的起始索引。
算法流程:
hash1
和 hash2
,分别记录 p
中字母的频次和窗口中字母的频次。s
,使用右指针 right
逐渐扩大窗口: p.size()
,则需要从左侧移出一个字母,并更新频次。hash1
和 hash2
相等时,说明当前窗口是 p
的一个异位词,记录其起始位置。
因为直接比较两个哈希表时间复杂度很高,这里我们想到了一种优化方式,要判断窗口字符串是否是异位词,我们只需要判断同一种字符在两个字符串中出现的次数是否一样即可,这里我们使用count
来统计有效字符的个数即可轻松判断窗口字符串是否是p
的异位词代码实现:
#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;
}
};
这里面count
是指有效字符的个数,很巧妙的判断滑动窗口里的字符串是否满足条件
O(n)
,每个字符最多被左右指针访问两次,因此时间复杂度为线性。O(1)
,只需要常数级别的额外空间用于存储两个固定大小的数组。假设输入为 s = "cbaebabacd"
, p = "abc"
,通过滑动窗口的执行过程如下:
Iteration | Left | Right | 窗口内字母频次 | 窗口大小 | 当前窗口字母 | 是否为异位词 | 异位词起始索引 |
---|---|---|---|---|---|---|---|
1 | 0 | 0 | [c] | 1 | c | 否 | - |
2 | 0 | 1 | [c, b] | 2 | cb | 否 | - |
3 | 0 | 2 | [c, b, a] | 3 | cba | 是 | 0 |
4 | 1 | 3 | [b, a, e] | 3 | bae | 否 | - |
5 | 2 | 4 | [a, e, b] | 3 | aeb | 否 | - |
6 | 3 | 5 | [e, b, a] | 3 | eba | 否 | - |
7 | 4 | 6 | [b, a, d] | 3 | bad | 否 | - |
8 | 5 | 7 | [a, b, a] | 3 | aba | 否 | - |
9 | 6 | 8 | [b, a, c] | 3 | bac | 是 | 6 |
10 | 7 | 9 | [a, c, d] | 3 | acd | 否 | - |
Right=0
到 Right=2
,窗口内包含 [c, b, a]
,它与 p="abc"
完全匹配,属于异位词,记录起始索引 0
。
Right=3
,窗口内包含 [b, a, e]
,字母 e
不在 p
中,因此当前窗口不是异位词。
Right=4
,窗口内包含 [a, e, b]
,依旧不匹配 p
,当前窗口不是异位词。
Right=5
,窗口内包含 [e, b, a]
,仍然不匹配 p
,当前窗口不是异位词。
Right=6
,窗口内包含 [b, a, d]
,d
不在 p
中,因此当前窗口不是异位词。
Right=7
,窗口内包含 [a, b, a]
,当前窗口不是异位词。
Right=8
,窗口内包含 [b, a, c]
,这再次是 p="abc"
的排列,属于异位词,记录起始索引 6
。
Right=9
,窗口内包含 [a, c, d]
,d
不在 p
中,因此当前窗口不是异位词。
题目链接:30. 串联所有单词的子串
题目描述:
给定一个字符串 s
和一个字符串数组 words
,words
中所有字符串的长度相同。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
仅包含小写英文字母。算法思路:
本题可以类比为寻找字符串中所有字母异位词的变种问题。不同的是,这里处理的对象是单词而不是单个字符。我们需要遍历字符串
s
,并通过滑动窗口找到所有符合条件的单词排列。
具体步骤:
hash1
记录 words
中每个单词的频次。s
,每次滑动窗口的大小为 words
中单词的总长度。hash2
,用于记录当前窗口内单词的频次。count
变量来统计有效字符串的个数即可算法流程:
hash1
,用于存储 words
中单词的频次。s
,通过滑动窗口按单词长度为步长,维护窗口内单词的频次。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
的长度,m
是 words
中单词的个数,l
是单词的长度。每个单词被扫描一次,并且最多执行 len
次完整的窗口扫描。O(m * l)
,用于存储 words
中单词的哈希表以及滑动窗口中的哈希表。假设输入为 s = "barfoothefoobarman"
, words = ["foo", "bar"]
,通过滑动窗口的执行过程如下:
具体过程和上一道题类似,核心没变,操作对象从单个字符变成字符串而已,以及一些细节的处理,其他都没啥了,这里就不详细分析了
Iteration | Left | Right | 窗口内单词 | 窗口大小 | 当前窗口单词 | 是否为串联子串 | 串联子串起始索引 |
---|---|---|---|---|---|---|---|
1 | 0 | 0 | [bar] | 1 | bar | 否 | - |
2 | 0 | 3 | [bar, foo] | 2 | barfoo | 是 | 0 |
3 | 6 | 9 | [foo, bar] | 2 | foobar | 是 | 9 |
[bar]
,不构成完整的串联子串。[bar, foo]
,它是 words
中单词的排列,记录起始索引 0
。[foo, bar]
,它是 words
中单词的排列,记录起始索引 9
。题目链接: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
s
和 t
由英文字母组成。算法思路:
这是一个典型的滑动窗口问题。目标是找到字符串
s
中能够覆盖t
所有字符的最小子串。解决思路如下:
t
中每个字符的频次,另一个用来动态维护滑动窗口中的字符频次。t
中每个字符的频次要求时,窗口就是一个可行的解。t
的要求,开始缩小窗口左边界,尽量缩短窗口长度。算法流程:
hash1
用来记录 t
中每个字符的频次,hash2
用来记录窗口内的字符频次。right
不断向右扩展窗口,同时更新窗口内的字符频次。t
中的要求,开始收缩左指针 left
,缩小窗口并更新最小子串的长度。这里面还是需要判断两个哈希表是否相等,我们这里还是采用的优化方式,使用count
变量来统计有效字符,不过之前两道题是为了统计字符出现的频次,这道题我们统计的是字符出现的种类,所以count
的++
和--
的情况有所变化喔
代码实现:
#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"
,滑动窗口的执行过程如下:
Iteration | Left | Right | 窗口内字符 | 窗口大小 | 是否为有效窗口 | 最小子串 |
---|---|---|---|---|---|---|
1 | 0 | 0 | [A] | 1 | 否 | - |
2 | 0 | 1 | [A, D] | 2 | 否 | - |
3 | 0 | 2 | [A, D, O] | 3 | 否 | - |
4 | 0 | 3 | [A, D, O, B] | 4 | 否 | - |
5 | 0 | 4 | [A, D, O, B, E] | 5 | 否 | - |
6 | 0 | 5 | [A, D, O, B, E, C] | 6 | 是 | ADOBEC |
7 | 1 | 6 | [D, O, B, E, C, O] | 6 | 否 | ADOBEC |
8 | 1 | 7 | [D, O, B, E, C, O, D] | 7 | 否 | ADOBEC |
9 | 1 | 8 | [D, O, B, E, C, O, D, E] | 8 | 否 | ADOBEC |
10 | 1 | 9 | [D, O, B, E, C, O, D, E, B] | 9 | 否 | ADOBEC |
11 | 1 | 10 | [D, O, B, E, C, O, D, E, B, A] | 10 | 是 | ADOBEC |
12 | 5 | 10 | [C, O, D, E, B, A] | 6 | 是 | ADOBEC |
13 | 6 | 10 | [O, D, E, B, A] | 5 | 否 | ADOBEC |
14 | 6 | 11 | [O, D, E, B, A, N] | 6 | 否 | ADOBEC |
15 | 6 | 12 | [O, D, E, B, A, N, C] | 7 | 否 | ADOBEC |
16 | 9 | 12 | [B, A, N, C] | 4 | 是 | BANC |
Left=0
开始向右扩展,但字符尚未覆盖 t="ABC"
的所有字符,因此没有有效窗口。Right=5
时,窗口内字符为 [A, D, O, B, E, C]
,此时首次找到覆盖 t
的有效窗口,记录最小子串为 "ADOBEC"
。t
的要求,最小子串保持为 "ADOBEC"
。Right=10
时,窗口内字符为 [D, O, B, E, C, O, D, E, B, A]
,再次满足条件,最小子串仍保持为 "ADOBEC"
。Left=5
,依然保持有效窗口,字符为 [C, O, D, E, B, A]
,最小子串保持不变。Right=12
时,窗口内字符为 [B, A, N, C]
,再次找到有效窗口,更新最小子串为 "BANC"
。在这篇博客中,我们继续探索了滑动窗口的高级应用,通过对一系列复杂问题的深度剖析,进一步展示了滑动窗口的灵活性与高效性。无论是「水果成篮」的双种类约束,还是「找到字符串中所有字母异位词」的字符频次比较,抑或是「串联所有单词的子串」的字符串匹配与「最小覆盖子串」的字符覆盖问题,这些问题都通过滑动窗口的精妙操作得到了优雅的解决。滑动窗口的核心在于对窗口边界的动态调整和哈希表的巧妙使用,结合不同场景的需求,展现了它在复杂算法挑战中的无限可能性。我们不仅解决了实际问题,更深入理解了滑动窗口的算法思想和设计精髓,为后续的算法学习打下了坚实基础。
以上就是关于【优选算法篇】踏入算法的深邃乐章:滑动窗口的极致探秘的内容啦,各位大佬有什么问题欢迎在评论区指正,或者私信我也是可以的啦,您的支持是我创作的最大动力!❤️