题目重点：Uber Graduate SDE OA 的最短窗口题要求至少 k 个不同值。用计数哈希表与左右指针在线性时间收缩窗口，明确与‘恰好 k 个子数组计数’不是同题。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入整数数组与正整数 k；只考虑非空连续子数组，满足不同整数个数至少 k，求最短长度。
- 若不存在返回 -1；k=1 时非空数组答案为 1，空数组无解。
- 题目提到 LC992 只是相似题参考；LC992 计数恰好 k 个不同值，而这里是最短长度且至少 k 个，目标不能混淆。
解题路线
- 右指针逐项加入窗口，哈希表保存每个值的出现次数；表的键数就是不同值数量。
- 只要键数≥k，当前窗口已可行：先更新最短长度，再不断移走左端并删除计数归零的键，直到窗口不可行。
- 对每个右端点，这个过程找出能保持可行的最右左边界；所有更长窗口不会改进答案，每个元素最多入窗、出窗各一次。
手动走一遍
[1,2,2,3,1,4]、k=3 时，窗口 [2,3,1] 长 3 已含三种值；任何长 2 窗口最多两个不同值，所以答案 3。若数组全是 5 且 k=2，返回 -1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Shortest contiguous subarray containing at least k distinct values."""
from collections import defaultdict
def shortest_at_least_k_distinct(values: list[int], k: int) -> int:
if k <= 0:
raise ValueError("k must be positive")
counts: dict[int, int] = defaultdict(int)
left = 0
best = len(values) + 1
for right, value in enumerate(values):
counts[value] += 1
while len(counts) >= k:
best = min(best, right - left + 1)
outgoing = values[left]
counts[outgoing] -= 1
if counts[outgoing] == 0:
del counts[outgoing]
left += 1
return -1 if best == len(values) + 1 else best
复杂度
左右指针各至多走 n 步，哈希操作期望 O(1)，总时间期望 O(n)，空间 O(min(n,D))，D 为输入不同值总数。若哈希退化则需按语言与容器实现讨论最坏界。
易错点与追问
容易失分的边界
- 频次降为 0 时必须删除键，否则 len(counts) 仍把已经离开窗口的值算成不同值。
- 先更新答案再收缩左端；若先移走一个元素再记录长度，可能跳过最短可行窗口。
- 题目是‘至少 k’，当不同值数大于 k 也要继续收缩，不是立即放弃。
继续深挖
- 若返回窗口下标，更新最短长度时同时保存 (left,right)，同长破平局可按最早起点。
- 若需在线查询多个 k，单次窗口算法要对每个 k 重跑；高频多 k 查询需分析值域和离线批量处理的成本。
