前言

最近朋友机试做了一条滑动窗口的题目。
题目给出一个字符串，求出所有长度为K的子串，输出这些子串中非重复元素的长度。
例如：abcdcdbas
有子串 abc bcd cdc dcd cdb dba bas
则输出3 3 2 2 3 3 3

数据规模：
k <= 字符串长度 <= 1e5

简单求所有子串，再遍历子串会被数据卡TLE
所以要在滑动窗口的基础上做一些优化，在求子串非重复长度上做个hash优化

求长度为K的子串，每个子串非重复元素的长度（要求，O(n)的时间复杂度）

代码思路：
在y总滑动窗口的模板下
用map记录每个字符的出现次数
出窗口的时候，对应字符–
进窗口的时候，对应字符++
若在一个窗口内，存在重复元素，map的值会大于2
所以==1的时候res_t 才+1

代码如下

/*
长度为k的子串，输出非重复元素的长度
*/
#include <unordered_set>
#include <iostream>
#include <cstring>
#include <algorithm>


using namespace std;

const int N = 100010;

int q[N], hh = 0, tt = -1;
char line[N];
int n, K;
int h[128];

int main()
{
    cin >> n >> K;
    cin >> line;
    int res_t = 0;
    for (int i = 0; i < n; i++) { // 滑动窗口
        if (tt >= hh && i - K + 1 > q[hh]) {//{h[q[hh--]]--;}
            if (h[line[q[hh]]] == 1) res_t--;
            h[line[q[hh++]]]--;
        }
        // 在窗口内，每进一个元素，加一
        q[++tt] = i;
        h[line[i]]++;
        if (h[line[i]] == 1) {
            res_t++;
        }
        if (i + 1 >= K) cout << res_t << ' ';
    }
}