《算法零基础100学》（第1学）滑动窗口（一）

目录

一.滑动窗口的算法模板：

1.模板一：

一.滑动窗口的算法模板：

1.模板一：

#include 
#include 
using namespace std;
string minWindow(string s, string t) {
    // 记录最短子串的开始位置和长度
    int start = 0, minLen = INT_MAX;
    int left = 0, right = 0;

    unordered_map window;
    
    unordered_map needs;//默认值为0;
    for (char c : t) needs[c]++;
    
    int match = 0;

    while (right < s.size()) {
        char c1 = s[right];
        if (needs.count(c1)) {
            window[c1]++;
            if (window[c1] == needs[c1])
                match++;
        }
        right++;

        while (match == needs.size()) {
            if (right - left < minLen) {
                // 更新最小子串的位置和长度
                start = left;//用star来标记最短字符串的位置，minlen则是它的长度
                minLen = right - left;
            }
            char c2 = s[left];
            if (needs.count(c2)) {
                window[c2]--;//c2个数--
                if (window[c2] < needs[c2])
                    match--;//匹配成功的字符数目减1；然后跳出循环
            }
            left++;//窗口继续向左滑动
        }
    }
    return minLen == INT_MAX ?
        "" : s.substr(start, minLen);
    
}

int main01() {
    string s, t;
    cin>>s>>t;
    string temp = minWindow(s, t);
    if (temp == "")    cout << "您要查找的子串不存在" << endl;
    else  cout << "包含目标字符串的最小子串为" << temp << endl;
    return 01;
}

借鉴资料：

【c++】STL 容器 unordered_map用法详解_炒扁豆的博客-CSDN博客_c++unordered_map用法

算法与数据结构（一）：滑动窗口法总结_dby_freedom的博客-CSDN博客_滑动窗口法