我们在做滑动窗口oj时,对最大最小滑动窗口总是傻傻分不清,总是把握不住什么时候缩小滑动窗口,什么时候控制下标,什么时候来判断,卡子今天来总结下滑动窗口oj,大小滑动窗口的解题框架
时间复杂度:o(n)
空间复杂度:o(n)
// 最小滑动窗口
// 为满足所求条件,先创建初始变量
for (size_t i = 0, j = 0; j < /*判断区间长度*/; j++)
{
// 将j位置元素计入窗口
while(/*满足所求条件*/)
{
// 判断并修改窗口长度
// 缩小窗口
}
}
//(判断是否找到合适窗口,未找到根据题意另外返回)
// 返回最终窗口/窗口长度
// 最大滑动窗口
// 为满足所求条件,先创建初始变量
for (size_t i = 0, j = 0; j < /*判断区间长度*/; j++)
{
// 将j位置元素计入窗口
while(/*不满足所求条件*/)
{
// 不得不缩小窗口
}
// 判断并修改窗口长度(保证每次满足所求条件下都有记录)
}
//(判断是否找到合适窗口,未找到根据题意另外返回)
// 返回最终窗口/窗口长度
套用最小滑动窗口框架框架
int minSubArrayLen(int target, vector<int>& nums)
{
// 求最小滑动窗口
int sum = 0;
// 求最小滑动窗口,初始化长度为最大值
int len = INT_MAX;
// i为开始位置,j为结束位置
for (size_t i = 0, j = 0; j < nums.size(); j++)
{
// 将j位置存入滑动窗口所求条件
sum += nums[j];
// i同时缩小(当i位置的元素删掉后不影响结果),归并到下面while中!!!
// 满足滑动窗口要求,满足要求下缩小滑动窗口
while ((long long)sum >= target)
{
// 判断并记录当前滑动窗口长度
len = j - i + 1 < len ? j - i + 1 : len;
// 缩小滑动窗口
sum -= nums[i];
++i;
}
}
// 如果未改变len,则说明未找到最小滑动窗口
if (INT_MAX == len)
{
return 0;
}
return len;
}
首先我们如果还是按照上面的框架来写
string minWindow(string s, string t)
{
// 最小滑动窗口
// 因为所求条件需要统计各个元素的次数,所以我们可以使用哈希表
unordered_map<char, int> window;
// 记录当前滑动所缺元素的数量(为了避免每次都在哈希表中找)
int cnt = t.size();
// 记录满足条件、当前滑动窗口下的返回字符串,初始化为空串(根据题意)
string ret("");
// 求最小滑动窗口,初始化长度为最大值
int len = INT_MAX;
// 将t统计进wind
for (auto& ch : t)
{
window[ch]++;
}
// 注:处理过程中,wind中的有效元素(t中元素)只可能为0 / 1
// i表示滑动窗口起始位置,j表示结束位置
for (size_t i = 0, j = 0; j < s.size(); j++)
{
// 先:判断j位置是否为有效元素(多余的有效元素也需记录),修改cnt
if (window[s[j]] >= 0) // ????????????
{
// 因为只有wind中所缺元素才可能>=0
--cnt;
}
// 再:将j位置元素引入所求条件中
window[s[j]]--;
for (auto& e : window)
{
cout << e.first << ":" << e.second << " ";
}
cout << endl;
cout << i << ":" << j << " cnt:" << cnt << endl;
// i同时缩小(当i位置的元素删掉后不影响结果),归并到while中!!!
// 当滑动窗口元素以满足所求条件,缩小滑动窗口
while (0 == cnt)
{
// 判断并记录当前滑动窗口长度、并修改返回字符串
if (j - i + 1 < len)
{
len = j - i + 1;
ret = s.substr(i, j);
}
// 缩小滑动窗口
// 判断如果i位置为有效元素,修改cnt;无效元素则直接缩小窗口
if (window[s[i]] >= 0)
{
window[s[i]]++;
// 只有我们初始将t统计进哈希表,t对应的元素此时才可能>=0
++cnt;
}
++i;
}
}
// 如果未找到合适子串,则返回初始的空串
return ret;
}
无法用相同框架来判断某位置为有效元素
所以我们为了方便判断某位置是否为有效元素,引用两个哈希表
string minWindow(string s, string t)
{
// 最小滑动窗口
// 注:有效元素指:s中某元素(删掉后,s中对应元素个数小于t中对应元素的个数)
// 因为所求条件需要统计各个元素的次数,所以我们可以使用哈希表
unordered_map<char, int> hs;
unordered_map<char, int> ht;
// 记录s在[i,j]区间中满足t的元素的个数(为了避免每次都在哈希表中找)
int cnt = 0;
// 记录满足条件、当前滑动窗口下的返回字符串,初始化为空串(根据题意)
string ret("");
// 求最小滑动窗口,初始化长度为最大值
int len = INT_MAX;
// 将t统计进wind
for (auto& ch : t)
{
ht[ch]++;
}
// i表示滑动窗口起始位置,j表示结束位置
for (size_t i = 0, j = 0; j < s.size(); j++)
{
// 先将j位置元素引入所求条件中
hs[s[j]]++;
// 再判断j位置是否为有效元素(多余的有效元素也需记录),修改cnt
// 因为我们先将s[j]加入hs数组中,再统计的,故等于也说明新加入的字符s[j]是必需的
if (hs[s[j]] <= ht[s[j]])
{
// 说明该结束位置为有效字符,但还未达到ht中的数量
++cnt;
}
// i同时缩小(当i位置的元素无效),归并到while中!!!
// 当滑动窗口元素已满足所求条件,缩小滑动窗口
while (t.size() == cnt)
{
// 判断并记录当前滑动窗口长度、并修改返回字符串
if (j - i + 1 < len)
{
len = j - i + 1;
ret = s.substr(i, j - i + 1);
}
// 缩小滑动窗口
// 判断如果i位置为有效元素,修改cnt,缩小窗口
if (hs[s[i]] <= ht[s[i]])
{
--cnt;
}
// 无效元素则直接缩小窗口
hs[s[i++]]--;
}
}
// 如果未找到合适子串,则返回初始的空串
return ret;
}
套用最大滑动窗口框架
int totalFruit(vector<int>& fruits)
{
// 最大滑动窗口
// 题意:找连续且只存两种元素的最大滑动窗口
// 为了记录窗口内各元素出现个数
unordered_map<int, int> wind;
int ret = 0;
// i表示窗口起始位置,j表示窗口结束位置
for (size_t i = 0, j = 0; j < fruits.size(); j++)
{
// 计入j位置元素
wind[fruits[j]]++;
// 同时增加i来不得不缩小窗口,在下while循环中统一进行
// 窗口不满足所求条件,不得不缩小窗口
while (wind.size() > 2)
{
// 不得不缩小窗口
// 先将key为i位置删掉一个val
wind[fruits[i]]--;
if (0 == wind[fruits[i]])
{
// 如果key为i,减去后val变为0.则将该pair删掉!!!~
wind.erase(fruits[i]);
}
++i;
}
// 记录当前滑动窗口长度,在while外记录,保证窗口在满足条件时每次都会记录!!!~
ret = j - i + 1 > ret ? j - i + 1 : ret;
}
return ret;
}
这里对文章进行总结:
以上就是今天总结的内容,本文包括了我自己对滑动窗口问题解题的小经验,分享给大家。
真💙欢迎各位给予我更好的建议,欢迎!小编创作不易,觉得有用可以一键三连哦,感谢大家。peace
希望大家一起坚持学习,共同进步。梦想一旦被付诸行动,就会变得神圣。
欢迎各位大佬批评建议,分享更好的方法!!!🙊🙊🙊