经典滑动窗口试题（二）

一、水果成篮

1、题目讲解

2、讲解算法思路

3、代码实现

class Solution {
public:
    int totalFruit(vector<int>& f) {
        int n=f.size();
        unordered_map<int,int> hash;
        int ret=0;
        for(int left=0,right=0;right<n;right++)
        {
            hash[f[right]]++;
            while(hash.size()>2)
            {
                hash[f[left]]--;
                if(hash[f[left]]==0)
                {
                    hash.erase(f[left]);
                }
                left++;
            }
             ret=max(ret,right-left+1);
        }
        return ret;
    }
    
};

二、找到字符串中所有字母异位词

1、题目讲解

2、讲解算法思路

3、代码实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[256]={0},len=p.size();
        for(char ch:p) hash1[ch]++;
        int hash2[256]={0};
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            char in=s[right];
            hash2[in]++;
            if(hash2[in]<=hash1[in]) count++;
            if(right-left+1>len)
            {
                char out=s[left];
                if(hash2[out]<=hash1[out]) count--;
                hash2[out]--;
                left++;
            }
            if(count==len)
            {
                ret.push_back(left);
            }
        }
        return ret;      
    }
};

三、串联所有单词的子串

1、题目讲解

2、讲解算法思路

3、代码实现

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1;
        for(auto ch:words)
        {
            hash1[ch]++;
        }
        int len=words[0].size(),m=words.size();
        for(int i=0;i<len;i++)
        {
            unordered_map<string,int> hash2;
             for(int left=i,right=i,count=0;right+len<=s.size();right+=len)
             {
                 string in=s.substr(right,len);
                 hash2[in]++;
                 if(hash1.count(in) && hash2[in]<=hash1[in]) count++;
                 if(right-left+1>len*m)
                 {
                     string out=s.substr(left,len);
                     if(hash1.count(out) && hash2[out]<=hash1[out]) count--;
                     hash2[out]--;
                     left+=len;
                 }
                 if(count==m) ret.push_back(left);
             }
        }
        return ret;
    }
};

四、最小覆盖子串

1、题目讲解

2、讲解算法思路

3、代码实现

代码一

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[256]={0};
        int kinds=0;
        for(auto ch:t)
        {
            if(hash1[ch]==0) kinds++;
            hash1[ch]++;
        }
        int hash2[256]={0};
        int minlen=INT_MAX,begin=-1;
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            char in=s[right];
            hash2[in]++;
            if(hash2[in]==hash1[in])  count++;
            while(count==kinds)
            {
                if(right-left+1<minlen)
                {
                    minlen=right-left+1;
                    begin=left;
                }
                char out=s[left++];
                if(hash2[out]--==hash1[out])  count--;    
            } 
        }
        if(begin==-1) return "";
        else return s.substr(begin,minlen);
    }
};

代码二 不使用kinds来计算种类

class Solution {
public:
    string minWindow(string s, string t) 
    {
        int hash1[256]={0},n=t.size();
        for(char ch:t)
        {
            hash1[ch]++;
        }
        int begin=-1,len=INT_MAX;
        int hash2[256]={0};
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            char in=s[right];
            hash2[in]++;
            if(hash2[in]<=hash1[in]) count++;
            while(count==n)
            {
                if(right-left+1<len)
                {
                    begin=left;
                    len=right-left+1;
                }
                char out=s[left];
                if(hash2[out]<=hash1[out]) count--;
                hash2[out]--;
                left++;
            }
        }
        if(begin==-1) return "";
        else return  s.substr(begin,len);
    }

};