【刷题篇】滑动窗口（二）

文章目录

1、水果成篮
2、找到字符串中所有字母异位词
3、串联所有单词的子串
4、最小覆盖子串

1、水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> ret;//这里可以使用数组，效率会有提高，
        int n=fruits.size();       //一直插入删除会有效率损失
        int maxi=0;
        int sum=0;
        for(int i=0,j=0;j<n;j++)
        {
            ret[fruits[j]]++;
            sum++;
            while(ret.size()>2)
            {
                ret[fruits[i]]--;
                sum--;
                if(ret[fruits[i]]==0)
                    ret.erase(fruits[i]);
                i++;
            }
            maxi=max(maxi,sum);
        }
        return maxi;
    }
};

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

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.size();
        int m = p.size();
        vector<int> arr;
        //unordered_map<char, int> ret;时间复杂度会过大
        int hash1[26];
        int hash2[26];
        for(auto& e:p)
            hash2[e-97]++;
        for(int i=0,j=0,cnt=0;j<n;j++)
        {
            if(++hash1[s[j]-97]<=hash2[s[j]-97])
                cnt++;
            if((j-i+1)>m)
            {
                if(hash1[s[i]-97]--<=hash2[s[i]-97])
                    cnt--;
                i++;
            }
            if(cnt==m)
                arr.push_back(i);
        }
        return arr;
    }
};

3、串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。
s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]，那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”，和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以任意顺序返回答案。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int n=s.size();
        int m=words[0].size();
        int len=words.size();
        vector<int> ret;
        unordered_map<string,int> hash1;
        for(auto& e : words)
            hash1[e]++;

        for(int k=0;k<m;k++)
        {
            unordered_map<string,int> hash2;
            for(int i=k,j=i,cnt=0;j<n;j+=m)//注意
            {
                string dummy=s.substr(j,m);
                hash2[dummy]++;
                if(hash1.count(dummy)&&hash2[dummy]<=hash1[dummy])
                    cnt++;
                if((j-i+1)>m*len)//注意
                {
                    string dummy1=s.substr(i,m);
                    if(hash1.count(dummy1)&&hash2[dummy1]<=hash1[dummy1])
                        cnt--;
                    hash2[dummy1]--;//注意
                    i+=m;//注意
                }
                if(cnt==len)
                    ret.push_back(i);
            }
        }
        return ret;
    }
};

4、最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

class Solution {
public:
    string minWindow(string s, string t) {//t是可重复的所以需要手动查找有效字符的个数
        int n=s.size();
        int m=0;//有效字符的个数
        int imax=INT_MAX;
        int begin=-1;
        int hash1[128];
        for(auto & e: t)
        {
            if(hash1[e]++==0)
                m++;
        }
        int hash2[128];
        for(int i=0,j=0,cnt=0;j<n;j++)
        {
            hash2[s[j]]++;
            if(hash1[s[j]]&&hash2[s[j]]==hash1[s[j]])
                cnt++;
            while(cnt==m)
            {
                if(imax>(j-i+1))
                {
                    imax=(j-i+1);
                    begin=i;
                }
                if(hash1[s[i]]&&hash2[s[i]]==hash1[s[i]])
                    cnt--;
                hash2[s[i]]--;
                i++;
            }
        }
        if(begin==-1)
            return "";
        else
            return s.substr(begin,imax);
    }
};