“滑动窗口”思想在算法里面的应用
目录
一· 无重复字符串的最长子串
链接：无重复字符的最长子串
1. 题目分析
解法一：暴力求解
借助2个“指针”：left ， right 指针，依次固定left 指针，让right指针进行遍历，每遇到一个最大的
字符串进行更新即可。
对应时间复杂度：O（N^2）
解法二：滑动窗口
2个指针移动方向一致，对right 指针所指向的元素进行遍历，对left 指针指向元素进行删除
此时借助一个临时数组判断是否有元素的重写。
2. 算法原理
暴力求解的草图：
模拟暴力求解的过程:
我们发现当出现重复元素的时候，每次right 指针重新回到新的left 所指向的
位置，在一次进行遍历的时候，求解最大长度的时候 只有2中可能的结果：要不就是等于初次的最
大长度；要不就是小于初次的最大长度
因为在[ left ,right ] 这个区间内left ++ 一次，都会让 [ left ,right ] 这个区间内l 元素的个数减少一
个。
因此我们可以进行优化：当遇到重复元素的时候，让right 指针不动，移动left 指针。
这正是“滑动窗口 ” 的应用。
时间复杂度：O(N)
此时我们需要借助一个临时的数组，来判断当前的元素是否重复。
出窗口结束条件：right 所指向的元素没有出现过就可以 ，此时删除left 所指向的没有元素。
3. OJ代码
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
//滑动窗口
int left = 0,right = 0,n = s.size();
int tmp[128] = {0};
int len = 0;
while(right < n)
{
//进窗口
tmp[ s[right]] ++;
//出窗口
while( tmp[ s[right]] > 1)
{
tmp[ s[left]]--;//tmp 当前位置元素为0
left++;
}
//更新
len = max (right-left+1,len);
right++;
}
return len;
}
};二· 最大连续1的个数
链接：最大连续1的个数
1. 题目分析
常规思路就是：遍历数组，遇到数字0 就改写成数字1，并记录一下Count 的大小当Count == 0的
个数的时候，就是这个区间里面1的个数。
草图：
换个思路就是：要求返回1所在区间里面 0 的个数<= k 的大小，之后便是找子区间里面1的个数最
多 的问题
解法一：暴力求解
固定left = 0，right = 0 ，count = 0
count 统计子数组里面0 的个数
解法二：滑动窗口
每一轮结束后找到指定区间的时候，right 指针都需要在会去left 指向下一个元素的位置，但是新
一轮区间里面1的个数是小于或者等于上一轮[ left, right ] 指向区间里面1的个数，因为此时指向的
区间只是相较于上一轮指向区间减少1个元素，所以针对这个情况，可以使用“滑动窗口”的思想
2. 算法原理
分为4小步：
1）“进窗口”
nums[right++] == 0
count ++；
2）判断
if(count > k)
3）“出窗口”
if(nums[left] == 0 )
count--;
4）结果更新
len = max(len,right -left);
3. OJ代码
3.1 解法一代码
int longestOnes(vector<int>& nums, int k)
{
int left = 0, right = 0, count = 0;//统计0 出现的次数
int len = 0;
for (; left < nums.size(); ++left)
{
right = left;
for (; right < nums.size(); ++right)
{
if (nums[right] == 0)
count++;
//结果更新
if (count > k)
{
len = max(len, right - left );
count = 0;//重新归为0
break;
}
}
}
return len;
}3.2 解法二代码
int longestOnes(vector<int>& nums, int k)
{
int left = 0, right = 0, count = 0;//统计0 出现的次数
int len = 0;
while (right < nums.size())
{
if (nums[right] == 0)
count++;
right++;
// if (count > k)
// {
// if (nums[left++] == 0)
// count--;
// }
//对于这个代码可以进优化，可能存在非连续的0
while(count > k)
{
if (nums[left++] == 0)
count--;
}
len = max(len, right - left);
}
return len;
}三· 将x 减小到0的最小操作数
链接：将x 减小到0的最小操作数
1. 题目分析
拿到此题目的时候，初始想法都是，遍历此数组，进行加和直至遍历所得的总和为 x 时候，返回此
时遍历元素的个数，即为题目所求。
图解分析：
2. 算法原理
其实换个思路就是：
找出一个最长的子数组的，同时这个子数组的所有元素之和恰好等于数组元素总和减去 x
len: 最长子数组的长度
add: 最长子数组的所有元素之和
sum : 数组所有元素之和
最小操作数：n - len
n : 数组的原始大小
1）解法一：暴力求解
“双指针”思想：固定left = 0,right = 0,add = 0,len = 0(记录最长子数组的元素个数）
对应时间 复杂度：O（N^2）
2）解法二：滑动窗口
还是一样的分析：每当add >= sum -x 的时候，right 都需要再次重新回到 left 所在元素的下一个位
置，再重新执行一样的操作，其实这个过程是没有必要的，此时只需要删除left 所指向的元素就
行，直至add <= sum -x.
3. OJ代码
暴力求解代码：
int minOperations(vector<int>& nums, int x)
{
//找出自由光最长子数组同时需要满足所有元素之和恰好为 sum - x
int n = nums.size();
if (x < nums[0] || x < nums[n - 1])
return -1;//不存在
int left = 0, right = 0, add = 0, sum = 0, len = 0;
for (auto it : nums)
{
sum += it;
}
if(x > sum)
return -1;
for (; left < n; ++left)
{
for (right = left; right < n; right++)
{
add += nums[right];
if (add > sum - x)
{
break;
}
if (add == sum - x)
{
len = max(len, right - left + 1);
break;
}
}
add = 0;
}
return n - len;
}滑动窗口代码：
int minOperations(vector<int>& nums, int x)
{
//滑动窗口
int n = nums.size();
int sum = 0, add = 0, len = 0;
for (auto it : nums)
sum += it;
if (x > sum)
return -1;
int left = 0, right = 0;
while (right < n)
{
add += nums[right++];
while (add > sum - x)
{
add -= nums[left++];
}
if (add == sum - x)
len = max(len, right - left);
}
return len == 0 ? -1:n - len;
}四. 找到字符串里面所有字母异位词
链接：找到字符串中所有字母异位词
1. 题目分析
常规思路：就是对s 这个字符串依次进行遍历，同时统计每一个有效字符出现的次数
对应的时间复杂度：O（N^2）
2. 算法原理
咱这里直接上“滑动窗口”的思想：
固定2个指针left = 0，right = 0；
定义2个数组 hash1[26] :用来存储p 这个字符串中每一个字符出现的次数
hash2[26]: 用来存储 s 这个字符串里面每隔 len 个字符里面有效字符出现的次数。
len : p 这个字符串的大小
同时借助一个变量 flag :默认2数组里面的元素相同（便于后期在进行检查的时候，好判断）
之所以把2个数组的大小固定为26：是因为题目中已经说明了：
3.OJ代码
vector<int> findAnagrams(string& s, string& p)
{
//滑动窗口 + 2个数组（统计每一个字符出现的次数）
int hash1[26] = { 0 };//统计p里面每一个字符出现的个数
int hash2[26] = { 0 };//统计s里面每len个字符里面 每一个字符出现的个数
int len = p.size();
//统计p 里面每一个字符的个数
int i = 0;
while (i < len)
{
hash1[p[i] - 'a'] ++;//映射的思想
i++;
}
int flag = 1;//标志位：默认2个字符数组相同
int left = 0;
int right = 0;
vector<int> ret;
while (right < s.size())
{
//进窗口
hash2[s[right] - 'a']++;
//判断&出窗口
if ((right - left + 1) > len)
{
//窗口大小是固定的，所以只需要删除一个元素就可以
hash2[s[left] - 'a']--;
left++;
}
//更新结果
if ((right - left + 1) == len)
{
int j = 0;
i = 0;
flag = 1;
//while (n--)//注意不能判断len 次，是对全部数组进行判断
while (i < 26)
{
if (hash1[i++] != hash2[j++])
{
flag = 0;
break;
}
}
if (flag == 1)
{
ret.push_back(left);
}
}
right++;
}
// 出了循环，还需要在进判断依次是否，满足一个有效的区间
if ((right - left + 1) == len)
{
int j = 0;
i = 0;
flag = 1;
//while (n--)//注意不能判断len 次，是对全部数组进行判断
while (i < 26)
{
if (hash1[i++] != hash2[j++])
{
flag = 0;
break;
}
}
if (flag == 1)
{
ret.push_back(left);
}
}
return ret;
}其实对于这个代码还是有优化的空间的。
此代码的时间复杂度是：O（N），准确的说是O(26N)
在进行结果更新的时候，可以采用一个Count 计数的方法
Count：记录子数组里面的有效字符的个数，这样就可以减少判断的次数。
需要在进窗口，出窗口，以及结果更新的时候，都需要对Count 进行维护。
注意Count 含义： 记录的是有效字符的个数
进窗口:
判断当前 right 所指向的元素在 hash2这个数组里面的指定位置出现的次数是否 <= hash1
这个数组里面指定位置出现的次数。若是满足count++
出窗口：
对left 指向的元素进行删除，注意Count-- 的条件
只有当 left 指向的字符出现的次数 <= 在p 这个字符串里面出现的次数，才可以Count --
结果更新：
当Count == len 的时候，left 所指向的元素就是一个有效的位置。
vector<int> findAnagrams(string& s, string& p)
{
//采用Count记录有效字符出现的个数
int count = 0;
int hash1[26] = { 0 };
int hash2[26] = { 0 };
int len = p.size();
//统计p 字符串里面每一个字符出现 次数
for (auto it : p)
hash1[it - 'a']++;
int right = 0, left = 0;
vector<int>ret;
while (right < s.size())
{
//进窗口
char in = s[right];
if (hash2[in - 'a']++ < hash1[in - 'a'])
count++;
//出窗口
if (right - left+1 > len)
{
char out = s[left++];
if (hash2[out - 'a']-- <= hash1[out - 'a'])
count--;
}
//结果更新
if (count == len)
ret.push_back(left);
right++;
}
return ret;
}结语：
以上就是关于“滑动窗口”部分应用的OJ题目，对于这一思想的掌握，需要我们在暴力算法思想的基础之上进行优化，所以“暴力求解”是我们进入“滑动窗口”世界之门的一把“钥匙”
，对于滑动窗
口的掌握，无非就是分4个小步骤：
1）进窗口
2）判断
3）出窗口
4）结果更新
可能结果更新这一步骤，不一定就是在“出窗口”之后，也可能在前面或者同时进行。总之，刷算法
题，画图结合思想是必不可少的，希望各位看到此篇博客，对于“滑动窗口”这一思想的理解和掌
握，可以有所帮助。