题目重点：用双指针求包含至少 k 个不同值的最短连续子数组，说明收缩顺序、频次归零与不可达返回。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- subarray 是非空连续区间；k≥1，训练接口对 k≤0 报错。
- 无法达到 k 种不同值时返回 -1；题目未指定该返回值。
- 元素可为任意整数，允许重复和负数；只关心不同值数。
解题路线
- 右指针逐个加入元素，哈希频次表记录当前窗口每个值的次数；只有次数从 0 变 1 时不同值数增加。
- 窗口达到至少 k 种后，先记录当前长度，再从左侧删除元素，持续缩到不再满足条件。这样枚举了每个右端点下所有可能的有效更短窗口。
- 某元素频次降到 0 时必须从表中删键；以表的键数代表不同值数才正确。
- 每个元素最多入窗一次、出窗一次，因此线性。
手动走一遍
[1,2,1,3]、k=3：右端到 3 时窗口 [1,2,1,3] 有 3 种，长度 4；移走左侧 1 后 [2,1,3] 仍有 3 种，更新为 3；再移走 2 后只剩 2 种。答案 3。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
from collections.abc import Sequence
def shortest_at_least_k_distinct(values: Sequence[int], k: int) -> int:
"""Minimum nonempty window length with >=k distinct values, else -1."""
if k < 1:
raise ValueError("k must be positive for nonempty windows")
counts: dict[int, int] = defaultdict(int)
left = 0
answer = len(values) + 1
for right, value in enumerate(values):
counts[value] += 1
while len(counts) >= k:
answer = min(answer, right - left + 1)
outgoing = values[left]
counts[outgoing] -= 1
if counts[outgoing] == 0:
del counts[outgoing]
left += 1
return -1 if answer > len(values) else answer
if __name__ == "__main__":
assert shortest_at_least_k_distinct([1, 2, 1, 3], 3) == 3
复杂度
O(n) 预期时间，哈希表最多保存 d 个不同元素，O(d) 空间；哈希最坏冲突行为取决于语言实现。
易错点与追问
容易失分的边界
- 把‘至少 k’误当‘恰好 k’，或者只在首次达标时记录一次。
- 频次减到 0 后仍留在字典，导致 len(counts) 假多。
- 先删左端再记录，漏掉刚达标的窗口。
- 无法满足时返回 n+1 这一内部哨兵，而未说明接口契约。
继续深挖
- 若要求返回所有最短窗口下标，怎样处理并列？
- 如果要统计恰好 k 种不同值的子数组总数，为什么需要 atMost(k)−atMost(k−1)？
- 输入是流且要不断查询当前最短历史窗口时，如何维护结果？
