滑动窗口算法

滑动窗口算法

滑动窗口算法框架

//滑动窗口算法框架
void slidingWindow(string s, string t){
    unordered_map<char,int> need, window;
    for(char c : t) need[c]++;
    int left=0, right=0;
    int valid=0;
    while(right < s.size()){
        //c是将移入窗口的字符
        char c=s[right];
        //右移窗口
        right++;
        //进行窗口内数据的一系列更新
        ...
        
        //判断左侧窗口是否要收缩
        while(window needs shrink){
            //d是将移出窗口的字符
            char d=s[left];
            //左移窗口
            left++;
            //进行窗口内数据的一系列更新
            ...
        }
    }
}

最小覆盖子串

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);
    }
};

字符串排列

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 d=s2[left];
                left++;
                //进行窗口内数据的一系列更新
                if(need.count(d)){
                    if(window[d]==need[d])
                        valid--;
                    window[d]--;
                }
            }
        }
        //未找到符合条件的子串
        return false;
    }
};

最长无重复子串

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){ //当window[c]值大于1时，说明窗口内存在重复字符，需要收缩
                char d = s[left];
                left++;
                //进行窗口内数据的更新
                window[d]--;
            }
            //更新答案
            res = max(res, right-left);
        }
        return res;
    }
};

找所有字母异位词

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 d=s[left];
                left++;
                //进行窗口内数据的更新
                if(need.count(d)){
                    if(window[d]==need[d]) valid--;
                    window[d]--;
                }
            }
        }
        return res;
    }
};

209.长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //deque<int> window;
        int left=0;
        int right=0;
        int res=INT_MAX;
        int sum=0;
        while(right<nums.size()){
            int c=nums[right];
            right++;

            //进行窗口内的更新
            //window.push_back(c);
            sum += c;
            while(sum>=target){
                res = min(res, right-left);
                int d=nums[left];
                left++;

                //进行窗口内的更新
                //window.pop_front();
                sum -= d;
            }
        }
        return res==INT_MAX ? 0 : res;
    }
};