面试经典 150 题 — 滑动窗口 (总结)

本文介绍: 面试经典 150 题 — 滑动窗口 (总结)

面试经典 150 题 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台

滑动窗口的思想，取i=j=0,向后遍历j,记录前缀和[l,r]为s,如果s>=target,那么左端点向右移动，直到s<target,维护一个[l,r]的滑动窗口，如此循环；

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n+1
        l=0
        s=0
        for r,x in enumerate(nums):
            s+=x
            while s>=target:
                ans = min(ans,r-l+1)
                s-=nums[l]
                l+=1
        return ans if ans <= n else 0

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0 ;
        int sum = 0;
        int l = 0 , r = 0 ; 
        int ans = INT_MAX ;
        while(r < n){
            sum += nums[r];
            while(sum >= target){
                ans = min(ans , r - l + 1) ;
                sum -= nums[l++];
            }
            r++ ;
        }
        return ans == INT_MAX ? 0 : ans  ;
    }
};

假设在一个无重复元素的字符串后面加上一个字符，如果出现重复元素，那么一定重复的是新加上的那个字符，那么设置一个hash表来统计次数，然后反复将窗口最前面的元素移出窗口，直到将前面与新加元素相同的元素移出时停止；然后循环更新答案即可；

力扣（LeetCode）官网 – 全球极客挚爱的技术成长平台

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        cnt = Counter()
        ans = 0
        for r , c in enumerate(s):
            cnt[c]+=1
            while cnt[c]>=2:
                cnt[s[l]]-=1
                l+=1
            ans = max(ans,r-l+1)
        return ans

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    unordered_map<char,int> hash;
    int ans=0;
    int n = s.size();
    int l=0;
    for(int r=0;r<n;r++){
        hash[s[r]]++;
        while(hash[s[r]] > 1) --hash[s[l++]];
        ans = max(ans,r-l+1);
    }
    return ans;
    }
};

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0 ;
        char[] st = s.toCharArray();
        boolean[] has = new boolean[128] ; 
        int n = s.length();
        int i = 0 ;
        for(int j=0;j<n;j++){
            char c = st[j];
            while(has[c])
                has[st[i++]] = false;
            has[c] = true;
            ans = Math.max(ans, j-i+1);
        }
        return ans;
    }
}

滑动窗口，细节看代码

class Solution {
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
        // 一个窗口包含s中的前a个单词;
        // 先删去前 i （i=0∼b−1）个字母后，
        // 将剩下的字母进行划分，如果末尾有不到 b 个字母也删去。
        vector<int> ans ;
        int a = words.size() , b = words[0].size() , n = s.size() ;
        for(int i=0;i<b&&i+a*b<=n;i++){ // 对应b种划分方法
            unordered_map<string,int> mp;
            for(int j=0;j<a;j++){//将s从i开始的a个长度为b的字符串放入哈希表中
                ++mp[s.substr(i+j*b,b)];
            }
            for(string& str : words){//将words中a个的字符串放入哈希表中，放入一个，对应的频次-1
                if(--mp[str]==0){
                    mp.erase(str);
                }
            }
            for(int start=i;start<n-a*b+1;start+=b){
                // 非第一个窗口
                if(start!=i){//因为上面已经考虑过start==i的情况了，这里直接跳过
                    string in = s.substr(start+(a-1)*b,b);//划入新的字符串
                    if(++mp[in]==0){//划入滑动窗口，就++
                        mp.erase(in);
                    }
                    string out = s.substr(start-b,b);
                    if(--mp[out]==0){
                        mp.erase(out);
                    }
                }
                if(mp.empty()){// 若窗口内单词与单词表中单词出现频次差皆为0，则为解
                    ans.push_back(start);
                }
            }
        }
        return ans ;
    }
};

滑动窗口 :

class Solution {
public:
    int get(char x) {
            return x >= 'A' && x <= 'Z' ? x - 'A' + 26 : x - 'a';
    }
    string minWindow(string s, string t) {
        int n = s.size() , cnt = 0 ;// cnt : 还需要匹配的字符种类数
        // 规定 a-z : 0-25  ,  A-Z : 26-51
        // c1 用于记录字符串 t 中字符的频率，c2 用于记录当前滑动窗口内字符的频率
        vector<int> c1(60),c2(60);
        for(char c : t) if(++c1[get(c)]==1) cnt ++ ;
        string ans = "" ;
        for(int i=0,j=0;i<n;i++){
            int idx1 = get(s[i]);//将s[i]加入窗口
            if(++c2[idx1]==c1[idx1]) cnt --;
            while(j<i){
                int idx2 = get(s[j]);
                // 尝试将s[j]划出窗口
                if(c2[idx2]>c1[idx2] && --c2[idx2]>=0){// 能够滑出窗口
                    //;
                    j++;
                }else{
                    break;//不能够滑出窗口
                }
            }
            if(cnt==0 && (ans.empty() || ans.size()>i-j+1)) ans = s.substr(j,i-j+1);
        }
        return ans ;
    }
};