🔥个人主页:Quitecoder
🔥专栏:算法笔记仓
目录
- `1.长度最小的子数组`
- `2.无重复字符的最长子串`
- `3.最大连续1的个数 III`
- `4.将 x 减到 0 的最小操作数`
- `5.水果成篮`
- `6.找到字符串中所有字母异位词`
- `7.串联所有单词的子串`
- `8.最小覆盖子串`
滑动窗口是一种常用的算法技术,它适用于需要检查序列(如数组或字符串)中的一系列连续元素的问题。通过维护序列中的一段特定大小的连续元素集,滑动窗口减少了不必要的重复计算,从而优化了性能。这种技术经常用于求解最大或者最小总和、长度满足特定条件的子串或子数组的问题。
操作滑动窗口通常涉及以下几个步骤:
-
初始化两个指针,通常称为
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.找到字符串中所有字母异位词
题目描述:
- 因为字符串 p 的异位词的长度⼀定与字符串 p 的⻓度相同,所以我们可以在字符串 s 中构
造⼀个长度为与字符串 p 的长度相同的滑动窗⼝,并在滑动中维护窗⼝中每种字⺟的数量; - 当窗口中每种字母的数量与字符串 p 中每种字⺟的数量相同时,则说明当前窗口为字符串 p
的异位词; - 因此可以用两个大小为 26 的数组来模拟哈希表,⼀个来保存 s 中的子串每个字符出现的个
数,另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词
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
相等 -
定义并初始化两个长度为 26 的数组
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)
获取该子串并返回。
- 当右指针遍历完