滑动窗口算法

参考文章：https://labuladong.gitee.io/algo/1/9/

滑动窗口算法主要解决子串（匹配）问题。 接下来给出滑动窗口算法的模板。以后遇到子串问题，直接套用模板即可。

void slidingwindow(string s ,string t){
    unordered_mapneed, window;
    for (char c: t)
        //如果c不存在，会自动创建key，并把map[key]赋值为0。相当于java中的map.put(key,map.getOrDefault(key,0)+1);
        need[c]++;
    //窗口的区间为[legt,right)。因此现在窗口为空
    int left=0,right=0;
    int vaild = 0;
    while (right< s.size()){
        //进入窗口的字符
        char c = s[right];
        right++:
        //对窗口内数据进行处理
        ...
        //判断左侧窗口是否要收缩
        while (window need shrink){
            char d = s[left];
            left++;
            //对窗口内数据进行处理
            ...
        }
    }
}

两处...的操作视具体情况而定。下面结合两道例题理解一下。

• 题目描述

给你一个字符串 s 、一个字符串 t 。
返回 s 中涵盖 t 所有字符的最小子串。
如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

下边套用模板来解决这个问题。

string minWindow(string s, string t) {
    unordered_mapneed, window;
    for (char c: t)
        need[c]++;
    int left=0,right=0;
    //表示满足need条件的字符个数
    int vaild = 0;
    int start = 0,len = INT_MAX;
    while (right< s.size()){
        //进入窗口的字符
        char c = s[right];
        right++:
        //对窗口内数据进行处理
        //need包含字符c，更新数据
        if (need.count(c)){
            window[c]++;
            if (window[c]==need[c])
                vaild++;
        }
        //判断左侧窗口是否要收缩
        while (vaild==need.size()){
            //更新最小覆盖子串
            if (right-left 
3.最长无重复子串 
题目描述
 
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 
这道题只有一个字符串。相比上一题比较简单，只需要改变一下模板即可。
 
void lengthOfLongestSubstring(string s){
    unordered_mapwindow;
    int left=0,right=0;
    //记录结果
    int res = 0;
    while (right< s.size()){
        //进入窗口的字符
        char c = s[right];
        right++:
        //判断左侧窗口是否要收缩(含有重复字符时收缩)
        while (window[c]>1){
            char d = s[left];
            left++;
            //对窗口内数据进行处理
            window[d]--;
        }
        //更新答案
        res = max(res,right-left);
    }
    return res;
}