滑动窗口算法

滑动窗口算法

滑动窗口算法框架

//滑动窗口算法框架
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++;
            //进行窗口内数据的一系列更新
            ...
        }
    }
}

//滑动窗口算法框架
func slidingWindow(s string, t string) {
    need := make(map[rune]int)
    window := make(map[rune]int)
    for _, c := range t {
        need[c]++
    }
    left, right := 0, 0
    valid := 0
    for right < len(s) {
        //c是将移入窗口的字符
        c := rune(s[right])
        //右移窗口
        right++
        //进行窗口内数据的一系列更新
        ...
        
        //判断左侧窗口是否要收缩
        for window needs shrink {
            //d是将移出窗口的字符
            d := rune(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);
    }
};

func minWindow(s string, t string) string {
    need := make(map[rune]int)
    window := make(map[rune]int)
    for _, c := range t {
        need[c]++
    }

    left, right := 0, 0
    valid := 0
    //记录最小覆盖子串的起始索引和长度
    start, length := 0, math.MaxInt32
    for right < len(s) {
        //c是将要移入窗口的字符
        c := rune(s[right])
        //右移窗口
        right++
        //进行窗口内的一系列更新操作
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
        //判断左侧窗口是否要收缩
        for valid == len(need) {
            //在这里更新最小覆盖子串
            if right-left < length {
                start = left
                length = right - left
            }
            //d是将移出窗口的字符
            d := rune(s[left])
            //左移窗口
            left++
            //进行窗口内数据的一系列更新操作
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }
    if length == math.MaxInt32 {
        return ""
    }
    return s[start : start+length]
}

字符串排列

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

func checkInclusion(s1 string, s2 string) bool {
    need := make(map[rune]int)
    window := make(map[rune]int)
    for _, c := range s1 {
        need[c]++
    }
    left, right := 0, 0
    valid := 0

    for right < len(s2) {
        c := rune(s2[right])
        right++
        //进行窗口内数据的更新操作
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
        //判断左侧窗口是否要收缩
        for right-left >= len(s1) {
            //判断是否找到了合法的子串
            if valid == len(need) {
                return true
            }
            d := rune(s2[left])
            left++
            //进行窗口内数据的一系列更新
            if _, ok := need[d]; ok {
                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;
    }
};

func lengthOfLongestSubstring(s string) int {
    window := make(map[rune]int)
    left, right := 0, 0
    res := 0 //记录结果
    for right < len(s) {
        c := rune(s[right])
        right++
        //进行窗口内数据的更新
        window[c]++
        //判断左侧窗口是否要收缩
        for window[c] > 1 { //当window[c]值大于1时，说明窗口内存在重复字符，需要收缩
            d := rune(s[left])
            left++
            //进行窗口内数据的更新
            window[d]--
        }
        //更新答案
        if right-left > res {
            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;
    }
};

func findAnagrams(s string, p string) []int {
    need := make(map[rune]int)
    window := make(map[rune]int)
    for _, c := range p {
        need[c]++
    }

    left, right := 0, 0
    valid := 0
    res := []int{} //记录结果
    for right < len(s) {
        c := rune(s[right])
        right++
        //进行窗口内数据的更新
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
        //判断左侧窗口是否要收缩
        for right-left >= len(p) {
            //当前窗口符合条件时，把起始索引加入到res
            if valid == len(need) {
                res = append(res, left)
            }
            d := rune(s[left])
            left++
            //进行窗口内数据的更新
            if _, ok := need[d]; ok {
                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;
    }
};

func minSubArrayLen(target int, nums []int) int {
    //deque<int> window;
    left := 0
    right := 0
    res := math.MaxInt32
    sum := 0
    for right < len(nums) {
        c := nums[right]
        right++

        //进行窗口内的更新
        //window.push_back(c);
        sum += c
        for sum >= target {
            if right-left < res {
                res = right - left
            }
            d := nums[left]
            left++

            //进行窗口内的更新
            //window.pop_front();
            sum -= d
        }
    }
    if res == math.MaxInt32 {
        return 0
    }
    return res
}