9. 滑动窗口

1. 76. 最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> need,window;
        for(char c:t){
            need[c]++;
        }
        int left=0,right=0;
        int valid=0;
        //记录最小覆盖字串的起始索引和长度
        int start=0,len=INT_MAX;
        while(right<s.size()){
            //c是将移入窗口的字符
            char c=s[right];
            //右移窗口
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]){
                    valid++;
                }
            }
            //判断窗口是否收缩
            while(valid==need.size()){
                //收缩窗口时更新数据，更新最小覆盖字串
                if(right-left<len){
                    start=left;
                    len=right-left;
                }
                //d是将要移出窗口的字符
                char d=s[left];
                //窗口左移
                left++;
                //进行窗口内数据的一系列更新
                if(need.count(d)){
                    if(window[d]==need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        //返回最小覆盖子串
        return len==INT_MAX?" ":s.substr(start,len);
    }
};

2. 567. 字符串的排列

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char,int> need,window;
        for(char c:s1){
            need[c]++;
        }
        int left=0,right=0;
        int valid=0;
        while(right<s2.size()){
            char c=s2[right];
            right++;
             // 进行窗口内数据的一系列更新
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]){
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while(right-left>=s1.size()){
                // 在这里判断是否找到了合法的子串
                if(valid==need.size()){
                    return true;
                }
                char c=s2[left];
                left++;
                // 进行窗口内数据的一系列更新
                if(need.count(c)){
                    if(window[c]==need[c]){
                        valid--;
                    }
                    window[c]--;
                }
            }
        }
        return false;
    }
};

3. 438. 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char,int> need,window;
        for(char c:p){
            need[c]++;
        }
        int left=0,right=0;
        int valid=0;
        //记录结果
        vector<int> res;
        while(right<s.size()){
            char c=s[right];
            right++;//扩大窗口
            // 进行窗口内数据的一系列更新
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]){
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while(right-left>=p.size()){
                // 当窗口符合条件时，把起始索引加入 res
                if(valid==need.size()){
                    res.push_back(left);
                }
                char c=s[left];
                left++;
                // 进行窗口内数据的一系列更新
                if(need.count(c)){
                    if(need[c]==window[c]){
                        valid--;
                    }
                    window[c]--;
                }
            }
        }
        return res;
    }
};

4. 3. 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> window;
        int left=0,right=0;
        int res=0;
        while(right<s.size()){
            char c=s[right];
            right++;
            // 进行窗口内数据的一系列更新
            window[c]++;
            // 判断左侧窗口是否要收缩,是否存在重复元素
            while(window[c]>1){
                char d=s[left];
                left++;
                // 进行窗口内数据的一系列更新
                window[d]--;
            }
            // 在这里更新答案，在判断完是否有重复元素后再更新
            res=max(res,right-left);
        }
        return res;
    }
};