解题思路
题意:给定长度为 n 的事件序列,每个事件用一个非负整数标签表示。研究人员只关注其中的 K 种标签(分别编号为 1 到 K),并给出每种关注标签的最低出现次数 c1,c2,…,cK。要求在一段连续子序列中,每种关注标签的出现次数都不低于对应的最低要求,求满足条件的最短连续子序列长度,若不存在则输出 −1。
核心算法:双指针滑动窗口
- 只关心 ci>0 的关注标签,其余视为无需约束。
- 先做一次可行性预检:统计整段序列每个关注标签的总出现次数
total[x],若存在 total[x] < c[x](且 c[x]>0),则必无解,直接输出 -1。
- 使用左右指针维护当前窗口
[l, r],并用 cnt[x] 统计窗口内每个标签出现次数。