之前博客已经介绍了采用双指针来解决链表类题目Link和数组类题目Link。
本博文介绍双指针中的变种：滑动窗口算法。
滑动窗口算法技巧主要用来解决子数组问题，比如让寻找符合某个条件的最长/最短子数组(如数组类题目Link中的最长回文子串)。
如果用暴力解的话，需要嵌套 for 循环这样穷举所有子数组，时间复杂度是 O(N^2)：
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
// nums[i, j] 是一个子数组
}
}
int left = 0, right = 0;
while (right < nums.size()) {
// 增大窗口
window.addLast(nums[right]);//插入右侧的数组
right++;
while (window needs shrink) {
// 缩小窗口
window.removeFirst(nums[left]);//从左侧删除数组
left++;
}
//虽然是两个while循环，但是left与right都只增不减，
//所以字符串/数组中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会说有某些元素多次进入和离开窗口，
//故此算法的时间复杂度就和字符串/数组的长度成正比。（感觉是O（2N）也就是相当于O（N））
}
注意：滑动窗口并不是穷举，有点类似于对穷举过程进行剪枝优化，避免冗余计算。
下面为滑动窗口的框架代码：
// 滑动窗口算法伪码框架
void slidingWindow(string s) {
// 用合适的数据结构记录窗口中的数据，根据具体场景变通
// 比如说，我想记录窗口中元素出现的次数，就用 map
// 如果我想记录窗口中的元素和，就可以只用一个 int
auto window = ...
int left = 0, right = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
window.add(c);
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...//进行窗口数据的更新
// *** debug 输出窗口的位置 ***
// 注意在最终的解法代码中不要 print， 因为 IO 操作很耗时，可能导致超时
//printf("window: [%d, %d)\n", left, right);
// ***********************
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
window.remove(d);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...//进行窗口数据的更新
}
}
}
滑动窗口算法最关键的是下面三个点：
- 1、什么时候应该扩大窗口？
- 2、什么时候应该缩小窗口？
- 3、什么时候应该更新答案？
1. 最小覆盖子串
Click to expand the code:时间复杂度O(N)，空间复杂度O(Min(M,N))
class Solution {
public:
string minWindow(string s, string t) {
// 先简单翻译一下题目:要在 S(source) 中找到包含 T(target) 中全部字母的一个子串，
// 且这个子串一定是所有可能子串中最短的
unordered_map<char,int>window, target;
// 确认target中的元素
for(char c:t)
{
target[c]++;
}
//定义左指针与右指针
int left=0,right=0;
//定义窗口中是目标的字符种类。因为有可能有多个
//由于target是去重的，为此只能通过种类来判断
int num_vail=0;// 记录window中的字符满足need条件的字符个数(注意不能是总的数目)
//截取的最小字符串，起点索引及长度（注意涉及循环中对比的都应该初始化值）
int start_index=0, min_len=INT_MAX;//将长度定义为最大的整数值，如果被修改了就是更新了
while(right<s.size())
{
char c=s[right];//将要加入到窗口中的
// 增大窗口
right++;//左闭右开，目前右边的值是不取的
window[c]++;
// 接下来进行窗口的数据更新
if(target.count(c))//如果在target有这个字符（注意要通过count来算是否存在才可以，通过访问值不行~）
{
// window[c]++;//此处无所谓，跟下面对称即可
if(window[c]==target[c])//如果字符每个种类的数目满足了
num_vail++;
}
//当 valid == need.size() 时，说明 T 中所有字符已经被覆盖，已经得到一个可行的覆盖子串，
//现在应该开始收缩窗口了，以便得到「最小覆盖子串」。
while(num_vail==target.size())//当满足找到全部目标值，开始移动左指针
{
//此时已经满足，为此进行覆盖
if(right-left<min_len)
{
start_index=left;
min_len=right-left;
}
char d=s[left];//将要移除窗口的
left++;//缩小窗口
//进行窗口数据更新
if(target.count(d))//如果这是需要的
{
if(window[d]==target[d])//每种字母只减一次
num_vail--;
// window[d]--;//从窗口中拿掉这个字符
}
window[d]--;//从窗口中拿掉这个字符
}
}
return min_len==INT_MAX ? "" : s.substr(start_index,min_len);
}
};
2.字符串的排列
Click to expand the code.解法跟上面一样，时间复杂度和空间复杂度也和上面一样~时间复杂度O(N)，空间复杂度O(Min(M,N))
class Solution {
public:
bool checkInclusion(string s1, string s2) {
// 采用滑动窗口算法
unordered_map<char,int> window, target;
for(char c:s1)
target[c]++;
// 定义窗口的左右两个指针
int left=0, right=0;
int num_vail=0;
while(right<s2.size())
{
char c=s2[right];
right++;
if(target.count(c))//如果是目标字符
{
window[c]++;//放入窗口中
if(window[c]==target[c])
num_vail++;
}
//判断左边窗口是否应该收缩（由于是全全排列，需要保证长度是一样的）
while(right-left>=s1.size())//尺寸更大了就应该缩小左边的窗口直到相等
//if(right-left>=s1.size())//用if也是一样的！！！由于维护的是一个定长的窗口，因此每次都前进一个字符而已~
{//一旦缩减了左边的窗口，就不等于目标值，说明他们中间有其他字符，因此当前不对了
//先判断是否目标
if(num_vail==target.size())//合法的排列
return true;
char d=s2[left];
left++;
if(target.count(d))//如果是目标字符
{
if(window[d]==target[d])
num_vail--;
window[d]--;//从窗口删除
}
}
}
return false;//如果上面循环没有true跳出
}
};
3. 找到字符串中所有字母异位词
跟上面两题很类似，只是形式不一样而已~所以结题思路跟复杂度都一样
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char,int> window,target;
for(char c:p)
target[c]++;
int left=0,right=0;
vector<int> result;
int num_vail=0;
while(right<s.size())
{
char in_window=s[right];//要进入窗口的
right++;
if(target.count(in_window))//如果是目标字符
{
window[in_window]++;//放入窗口中
if(window[in_window]==target[in_window])
num_vail++;
}
//缩小左边窗口的条件（固定尺寸了，一旦满足就开始检测！）
if(right-left>=p.size())
{
//判断是否成功获得结果
if(num_vail==target.size())
{
result.push_back(left);//将此时起始位置放入
}
char out_window=s[left];
left++;
if(target.count(out_window))
{
if(window[out_window]==target[out_window])
num_vail--;
window[out_window]--;
}
}
}
return result;
}
};
4.无重复字符的最长子串
原本的解法有两个：
解法1：暴力匹配，时间复杂度为O（N2）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
string temp_str;
size_t max_len=0;//注意不是int
// 暴力匹配
for(int i=0; i<s.size();i++)
{
temp_str=s[i];//当前字符串
for(int j=i+1; j<s.size();j++)
{
if(temp_str.find(s[j])!=temp_str.npos)//注意终点位置为npos
{//不为终点，那么就是找到了
max_len=max(max_len,temp_str.size());//保留最长的
break;//跳出当前循环
}
//找不到,那么就添加
temp_str=temp_str+s[j];//一直添加
}
max_len=max(max_len,temp_str.size());//最后一个测试
}
return max_len;
}
};
解法2：采用hash table，时间复杂度为O（N）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
string temp_str;
size_t max_len=0;//注意不是int
//用hash table复杂度为O（n）
unordered_map<char,int> map;//传入的为字符及对应的索引
for(int i=0;i<s.size();i++)
{
if(map.find(s[i])!=map.end())//不为尾部，那么就是找到了
{
int index=map[s[i]];//获取找到的索引
i=index+1;//下一次从它的下一个开始
max_len=max(max_len,map.size());//记录最大值
map.clear();//清空掉，重新算
}
map[s[i]]=i;//记录当前字符及其索引
}
max_len=max(max_len,map.size());//最后出来的时候再次double check
return max_len;
}
};
解法3：采用滑动窗口算法。时间复杂度为O（N）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> window;
int max_len=0;//注意不是int
int left=0,right=0;
while(right<s.size())
{
char in=s[right];
right++;
window[in]++;//将元素放入window中
//缩小左边窗口的条件
while(window[in]>1)//重复了因此需要进一步缩小窗口
{
char out=s[left];
left++;
window[out]--;
}
//此时获得了一个不重复的窗口
// 每次循环都会更新这个，因此在进入上面循环之前，保留了最大的~
//而收缩完则可以保证窗口中必然没有重复的元素
max_len=max(max_len,(right-left));
}
return max_len;
}
};