至少K种不同值的最短子数组：单调滑窗

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• K为正整数；连续非空区间至少K种不同值；不存在返回None。
• 返回半开下标；等长取首次发现的区间。元素必须可哈希。

解题路线

1. 右端扩张只会保持或增加不同值数，左端收缩只会保持或减少，因此满足≥K时可以尝试缩到最短。
2. 计数表必须删除次数归零的键，否则len(counts)不再代表不同值数。每次满足时记录候选后删左端，一直直到不满足。
3. 任何最优区间会在其右端加入时被连续收缩过程访问。每个元素最多进入和离开各一次，给出线性摊还证明。

手动走一遍

[1,2,2,3],K=3：先发现全段长4，删第一个1后种数降2，因此答案(0,4)。[1,2,1,3],K=3：首次全段长4，缩到[2,1,3]仍有3种，更新长度3。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def shortest_distinct(a, k):
    if k <= 0:
        raise ValueError("positive k required")
    counts, left, best = {}, 0, None
    for right, x in enumerate(a):
        counts[x] = counts.get(x, 0) + 1
        while len(counts) >= k:
            if best is None or right + 1 - left < best[1] - best[0]:
                best = (left, right + 1)
            y = a[left]
            counts[y] -= 1
            if not counts[y]:
                del counts[y]
            left += 1
    return best

复杂度

期望O(n)时间、O(d)空间，d为窗口内不同值上限；没有解时仍可能存所有不同值。

易错点与追问

容易失分的边界

• 记录答案应在删除左端之前，否则丢掉临界有效窗口。
• “恰K种的最长窗口”与本题的目标、收缩时机均不同。

继续深挖

• 若K=0允许空区间，接口应怎样定义返回？
• 如何统计恰好K种的全部区间数，而非只返回最短？