单词背诵

这是滑动窗口问题，找到包含最多目标单词的最短连续段落，先用哈希表标记所有需要背的单词 ，用队列维护当前窗口，遍历文章单词时入队，并更新目标单词的出现次数， 窗口右移时，尝试收缩左边界，移除那些出重复出现或非目标单词的元素，保证窗口内单词尽可能紧凑。

记录最大覆盖数 se 和对应的最短窗口长度 ans。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    string s;
    unordered_map<string,int>cnt; // 要背的单词及出现次数
    int se=0; // 记录当前窗口包含的要背单词总数
    for(int i=0;i<n;i++){
        cin>>s;
        cnt[s]=1; 
    }
    queue<string>q; // 滑动窗口的队列
    int t;
    cin>>t;
    int ans=INT_MAX; 
    for(int i=0;i<t;i++){
        cin>>s;
        q.push(s); 
        if(cnt[s]==1){se++;ans=q.size();} // 更新当前窗口长度
        if(cnt[s]!=0)cnt[s]++; // 计数+1
        
        // 收缩窗口左边界
        while(!q.empty() && (cnt[q.front()]>2 || cnt[q.front()]<=0))
            {cnt[q.front()]--;q.pop();}
        int a=q.size();
        ans=min(ans,a); // 更新最短窗口长度
    }
    cout<<se<<'\n'<<ans; 
    return 0;
}

时间复杂度：O(t) 空间复杂度：O(n+t)