滑动窗口 | ae86's Blog

简介

滑动窗口算法本质上还是基于左右指针的算法，就是用左右指针规定窗口范围，减少一些不必要的比较，提升算法的时间复杂度。该算法通常用于解决一些子串问题。

注：子串与子序列不同，子串是要求连续的，子序列不要求连续。子串 == 子数组

框架

//滑动窗口算法框架
void slidingWindow(string s, string t){
    //window表示窗口里的元素当前的个数，通常我们只记录有意义的信息
    //need表示不同元素所需要的个数，需要满足要求
    unordered_map<char, int> need, window;
    //将子串所需要的，用need来表示
    for(char c : t) need[c]++;
    //这里采用的是左闭右开的区间表示方式，目前没有任何元素
    int left = 0,right = 0;
    int valid = 0;
    while(right < s.size()){
        //移入窗口的元素
        char c = s[right];
        right++;
        //对窗口内的数据的一系列更新
        ...

        //用于debug
        cout << left << " " << right << endl;
        
        //判断哪些是要收缩的
        while(window needs shrink){
            //移出窗口的元素
            char d = s[left];
            left++;
            //对窗口进行一系列更新
            ...
		}
    }
}

注：窗口的长度可以用right - left来表示。

寻找窗口中的元素在子串中

//窗口中添加元素
if(need.count(c)){
    window[c]++;
    if(window[c] == need[c]){
        valid++;
    }
}
//窗口中减少元素
if(need.count(d)){
    if(window[d] == need[d]){
        valid--;
    }
    window[d]--;
}