目录
滑动窗口是一种常用的算法技术,它适用于需要检查序列(如数组或字符串)中的一系列连续元素的问题。通过维护序列中的一段特定大小的连续元素集,滑动窗口减少了不必要的重复计算,从而优化了性能。这种技术经常用于求解最大或者最小总和、长度满足特定条件的子串或子数组的问题。
操作滑动窗口通常涉及以下几个步骤:
left
和 right
,指向序列的起始部分,这定义了窗口的边界。
right
指针向右移动以扩大窗口,直到窗口中的元素满足特定条件(例如,元素总和达到目标值)。
left
指针向右移动以缩小窗口,并再次检查条件是否满足。在移动 left
指针的同时,我们可以更新相关的计算结果,如累积和或计数器等
left
和 right
指针,直到滑动窗口穷尽了整个序列的所有可能的连续元素集
一个常见的滑动窗口问题示例是找出一个数组中和至少为 target
的最短连续子数组,在这样的问题中,滑动窗口技术能够有效地找到解决方法,同时保证时间复杂度最少。
1.长度最小的子数组
题目链接:209. 长度最小的子数组 题目描述:
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int right =0,left=0,len=INT_MAX;
int sum=0;
while(right<nums.size())
{
sum+=nums[right];
while(sum>=target)
{
len=min(len,right-left+1);
sum-=nums[left++];
}
right++;
}
return len==INT_MAX?0:len;
}
};
这段代码解决的问题是寻找数组 nums
中和至少为 target
的最短连续子数组的长度。使用了滑动窗口方法,以下是它的逻辑和思路:
left
和 right
, 以及 sum
来存储当前窗口中的元素和,和 len
来存储最短子数组的长度。这里,len
初始化为 INT_MAX
,表示一个非常大的数,用来保证能找到比初始值小的最小长度
while
循环遍历数组,右指针 right
逐渐向右移动,遍历数组的每个元素。
right
指向的当前元素加到 sum
中。这扩大了当前的滑动窗口,包括了 right
指向的新元素
target
时,进入内层 while
循环。在内层循环中:
a. 通过 min(len, right-left+1)
更新 len
的值,以保持记录最短连续子数组的长度。
b. 尝试缩小窗口从而找到可能的更短的连续子数组,方法是减去滑动窗口左端的元素值 nums[left]
,然后将左指针向右移动一位 (left++
)
while
循环,右指针向右移动 (right++
)。每次增加 right
时,重复上述过程,更新窗口中的元素和 sum
,然后再次检查窗口的和是否大于等于 target
while
循环结束时(即遍历了所有元素),检查最短长度 len
是否被更新过:如果 len
还是 INT_MAX
,这意味着没有找到满足条件的子数组,函数返回 0;否则,返回找到的最短连续子数组的长度
这个时间复杂度是 O(n),因为每个元素最多被访问两次:一次是右指针向右移动时,另一次是左指针向右移动时
2.无重复字符的最长子串
题目链接:3. 无重复字符的最长子串 题目描述:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128]={0};
int left=0,right=0,len=0;
while(right<s.size())
{
hash[s[right]]++;
while(hash[s[right]]>1) hash[s[left++]]--;
len=max(len,right-left+1);
right++;
}
return len;
}
};
寻找给定字符串 s
中最长不含重复字符的子串的长度。使用滑动窗口,并在窗口内部跟踪了字符的出现情况。具体思路:
hash
数组用来维护每个 ASCII 字符在当前考虑的子串(滑动窗口)中的出现次数。它被初始化为0。
left
和 right
两个指针用来表示滑动窗口的边界,初始时都指向字符串的开头
len
用来保持找到的最长不重复字符子串的长度
while
循环用于移动 right
指针,这扩大了当前考虑的窗口
hash
数组中增加 right
指向字符的计数
while
循环检查通过 right
新加入的字符是否导致了重复字符出现。如果是这样,循环就使用 left
指针向前移动直到这个字符的计数再一次变为1
len
比较,取较大者作为新的 len
right
指针向前移动一位,以便包含当前右边界的下一个字符。
right
到达字符串的末尾结束,这时所有可能的窗口都已经被考虑。
len
就是最长不重复字符子串的长度。
代码结束时返回的 len
是所求的最长子串长度
3.最大连续1的个数 III
题目链接:1004. 最大连续1的个数 III 题目描述:
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left=0,right=0,len=0,zero=0;
while(right<nums.size())
{
if(nums[right]==0)zero++;
while(k<zero)
{
if(nums[left]==0) zero--,left++;
else left++;
}
len=max(len,right-left+1);
right++;
}
return len;
}
};
同样的思路,用zero来记录零的个数,如果zero大于二,移动左指针指导等于二位置,继续将right向右移动,最后返回len的最大值
4.将 x 减到 0 的最小操作数
题目链接:1658.将 x 减到 0 的最小操作数 题目描述:
正难则反:
本题可以转换为,求中间最长连续数组的和为数组总和减去x的结果
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum=0;
for(int e:nums)
{
sum+=e;
}
int des=sum-x;
if(des<0)
return -1;
int left=0,right=0,len=-1,add=0;
while(right<nums.size())
{
add+=nums[right];
while(add>des)
{
add-=nums[left++];
}
if(add==des)
{
len=max(len,right-left+1);
}
right++;
}
return len==-1?-1:nums.size()-len;
}
};
des是中间连续数组的目标求和值,add记录连续子数组的和,如果和大于目标值,则让add减去左指针指向的值并让左指针移动,如果等于则记录最大值,这里初始值给-1,如果没有匹配的数组,则返回-1
5.水果成篮
题目链接:904.水果成篮 题目描述:
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int hash[100001]={0};
int left=0,right=0,len=0,kinds=0;
while(right<fruits.size())
{
if(hash[fruits[right]]==0) kinds++;
hash[fruits[right]]++;
while(kinds>2)
{
hash[fruits[left]]--;
if(hash[fruits[left]]==0)
kinds--;
left++;
}
len=max(len,right-left+1);
right++;
}
return len;
}
};
在给定一个整数数组 fruits
的情况下,找到最长的连续子数组(窗口),其中只包含最多两种不同的元素(即果树种类)。这个问题可以用滑动窗口算法解决:
hash
数组用来计数每种水果当前在窗口中的数量。
left
和 right
表示当前窗口(子数组)的两端位置。
len
用来记录窗口的最大长度。
kinds
用来记录当前窗口中有多少种不同的水果
代码的逐步逻辑:
while
循环通过移动 right
指针向右扩展窗口,这样就能包含新的元素(水果种类)。
right
指针指向的水果种类之前未包含在窗口中(即 hash[fruits[right]] == 0
),则增加 kinds
变量。
hash[fruits[right]]++
)。
while
循环检查 kinds
是否超过了2。如果是这样,这表示当前窗口包含了超过两种水果,不符合题目条件。在这种情况下,需要缩小窗口(移动 left
指针)直到窗口中只包含两种水果。
if(hash[fruits[left]] == 0)
这句代码检查减去左指针后是否已经不包含这种水果,如果不包含,则种类数 kinds
需要减少
len
(max(len, right - left + 1)
)。
right
指针继续向右移动,让外部循环继续执行。
len
中存储的就是满足条件的最大窗口长度。
6.找到字符串中所有字母异位词
题目链接:438.找到字符串中所有字母异位词 题目描述:
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if (s.length() < p.length()) {
return result;
}
int left = 0, right = 0, n = p.size(), count = 0;
int hash1[26] = {0};
int hash2[26] = {0};
for (char e : p) {
hash1[e - 'a']++;
}
while (right < s.length()) {
hash2[s[right] - 'a']++;
if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) {
count++;
}
if (right - left + 1 > n) {
if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a']) {
count--;
}
hash2[s[left] - 'a']--;
left++;
}
if (count == n) {
result.push_back(left);
}
right++;
}
return result;
}
};
:
s
的长度是否小于 p
的长度,如果小于,则直接返回空结果集,因为 p
的异位词长度必定与 p
相等
hash1
和 hash2
,这两个哈希表用于存储字符 ‘a’ 到 ‘z’ 在字符串 p
和当前检查的 s
的子串中出现的次数
p
并更新 hash1
表,其中 hash1[e - 'a']++
表示将字符 e
在 hash1
中的计数增加 1,用于记录 p
里每个字符的频率
left
和 right
定义滑动窗口的边界。left
是窗口的起始位置,right
是窗口的结束位置,初始化时它们都是 0。变量 n
存储字符串 p
的长度,count
用于记录当前滑动窗口内字符频率匹配 p
中的字符频率的数量(即异位词的字符计数)
s
,同时动态更新 hash2
表,并增加 count
计数,表达式 hash2[s[right] - 'a']++
用于更新 s
中当前字符的频率
hash2
里的计数小于或等于 hash1
中的对应计数,count
增加 1,这意味着这个字符是 p
中的字符,并且在目前窗口中的出现频率尚未超过 p
中的频率
p
的长度时,必须移动窗口的左边界。如果要移出窗口的字符的频率在 hash2
中小于或等于 hash1
,则减少 count
计数,并将 hash2[s[left] - 'a']
减少 1,表示该字符从窗口中移除。
count
与 p
的长度相等,这意味着当前窗口是 p
的一个异位词,将当前窗口的起始索引 left
添加到结果集中。
result
与前面不同的是,这道题的窗口大小可以看做是固定的,left每次向右移动保证了窗口大小
7.串联所有单词的子串
题目链接:30.串联所有单词的子串 题目描述:
代码思路:与上一道题类似,我们把每个words里面的元素当成一个整体,然后对s进行整体的划分即可
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
if(s.empty() || words.empty() || words[0].size() > s.size())
return ret;
unordered_map<string, int> hash1; // 保存 words 里面所有单词的频次
for(auto& word : words) hash1[word]++;
int len = words[0].size(), m = words.size();
int i = 0;
while(i < len) { // 执行 len 次
unordered_map<string, int> hash2; // 维护窗口内单词的频次
int left = i, right = i, count = 0;
while(right + len <= s.size()) {
// 进窗口 + 维护 count
string in = s.substr(right, len);
if(hash1.count(in)) {
hash2[in]++;
if(hash2[in] <= hash1[in]) count++;
}
// 判断
if(right - left + 1 > len * m) {
// 出窗口 + 维护 count
string out = s.substr(left, len);
if(hash1.count(out) && hash2[out] > 0) {
if(hash2[out] <= hash1[out]) count--;
hash2[out]--;
}
left += len;
}
// 更新结果
if(count == m) ret.push_back(left);
right += len; // 窗口右端向右移动
}
i++; // 处理下一个子串开始位置
}
return ret;
}
};
继续构建两个哈希表
“执行 len 次”是指,对滑动窗口处理的起始点进行遍历,而遍历的次数等于单词的长度 len。每个单词长度相同,这个长度用 len 变量表示
8.最小覆盖子串
题目链接:76.最小覆盖子串 题目描述:
class Solution {
public:
string minWindow(string s, string t) {
string s1;
if(s.size()<t.size())return s1;
int hash1[128]={0};
int hash2[128]={0};
int kinds=0;
int count=0;
int len=INT_MAX;
for(auto e:t)
{
if(hash1[e]++ == 0) kinds++;
}
int left=0,right=0;
int start=0;
while(right<s.size())
{
hash2[s[right]]++;
if(hash2[s[right]]==hash1[s[right]])count++;
while(count==kinds)
{
if(right - left + 1 < len) {
len = right - left + 1;
start = left;
}
hash2[s[left]]--;
if(hash2[s[left]]<hash1[s[left]])count--;
left++;
}
right++;
}
return len==INT_MAX?"":s.substr(start,len);
}
};
思路:
s
的长度是否小于 t
的长度。若是,则无法包含所有 t
中的字符,直接返回空字符串。hash1
和 hash2
来分别记录 t
中每个字符的频率和当前窗口中每个字符的频率。数组大小设置为 128,以便覆盖所有 ASCII 字符。t
中字符的频率:
t
,并使用 hash1
统计每个字符出现的频率。e
在 hash1
中的频率从 0 变为 1,意味着 t
中又有一个新的字符,因此将 kinds
计数加 1,kinds
表示 t
中不同字符的种类数。count
为 0,用于记录当前窗口已满足的 t
中不同字符的数量。len
为 INT_MAX
,用于记录目前找到的最小窗口的长度。left
和 right
为 0,它们表示滑动窗口的左右边界。right
:
while
循环,移动右指针 right
来拓展当前窗口,直到涵盖了 t
中的所有字符。hash2[s[right]]
的值,表示当前字符在窗口中的计数增加。s[right]
在 hash2
中的计数与 hash1
中的计数相等,意味着至少包含了 t
中对应字符所要求的数量,count
加 1。count
与 kinds
相等时,意味着当前窗口覆盖了 t
中所有的字符。while
循环,尽可能缩小窗口大小,移动左指针 left
,同时更新 len
和 start
来记录最小覆盖子串的位置和长度。left
指针之后,将 hash2[s[left]]
相应的值减少。如果减少后 hash2[s[left]]
的值小于了 hash1[s[left]]
,意味着不能再移动 left
指针,因为移除的字符是 t
中必须有的字符,所以窗口不再满足条件,需停止收缩。right
,寻找下一个满足条件的窗口。s
后,检查记录的 len
是否变化,如果为 INT_MAX
,表示没有找到合适的窗口,返回空字符串。len
不为 INT_MAX
,意味着找到了最小窗口子串,通过 s.substr(start, len)
获取该子串并返回。