掌握滑动窗口：高效解决“恰好包含 K 个不同整数的子数组”问题

在这篇文章中，我们将深入探讨一个非常经典且具有挑战性的算法问题：如何在数组中找出恰好包含 K 个不同整数的子数组数量。这不仅仅是一道面试题，更是掌握滑动窗口这一核心算法思想的绝佳练习。

通过阅读这篇文章，你将学会：

• 如何从暴力解法一步步推导出最优解。
• 滑动窗口的核心技巧，特别是“最多 K 个”减去“最多 K-1 个”这一巧妙转化。
• 如何处理复杂的窗口收缩逻辑，并理解其背后的数学原理。
• 避免常见的逻辑陷阱，编写出既高效又易读的代码。

问题描述

给定一个正整数数组 INLINECODEd664d2da 和一个数字 INLINECODE463c0ed3，我们的任务是统计数组中恰好包含 K 个不同元素的子数组的数量。

1 <= K <= 数组中不同元素的总数

为了确保我们都在同一个频道上，让我们先通过几个具体的例子来明确题目要求。

示例分析

示例 1：

输入：INLINECODE4f5c5a78, INLINECODE95237ad5

输出：7

解释：

让我们手动列出所有符合条件的子数组（为了方便，我们用元素的值表示子数组）：

• [2, 1] （索引 0-1）
• [1, 2] （索引 1-2）
• [2, 1, 2] （索引 0-2，包含 1 和 2）
• [2, 1] （索引 2-3）
• [1, 6] （索引 3-4）
• [1, 2, 1, 6] （索引 1-4，包含 1, 2, 6 —— 等等！这是 3 个不同元素）

* 这里要注意，只有包含恰好 2 个不同元素的才算。

* 让我们重新仔细检查一下 arr = [2, 1, 2, 1, 6] 中 K=2 的情况：

* 长度为 2 的：INLINECODE9d295ef7, INLINECODE4c54277b, INLINECODE5c9be5a4, INLINECODE15879c5e (共4个)

* 长度为 3 的：INLINECODE26b3abea (1,2), INLINECODE2d48cd67 (1,2) (共2个)

* 长度为 4 的：[2,1,2,1] (1,2) (1个)

* 总共 4 + 2 + 1 = 7 个。完全正确。

示例 2：

输入：INLINECODEc4424466, INLINECODE377c4144

输出：5

解释：

这很简单。因为所有元素都是不同的，只有长度为 1 的子数组才满足“恰好 1 个不同元素”。数组长度为 5，所以答案就是 5。

初步思路：暴力解法

面对任何算法问题，最直观的思路往往是暴力穷举。我们可以尝试生成所有可能的子数组，然后逐个检查它们包含多少个不同的元素。

算法步骤

• 使用两层循环。外层循环 i 从 0 到 n-1，确定子数组的起点。
• 内层循环 INLINECODE6086b049 从 INLINECODE45dd5ad6 到 n-1，确定子数组的终点。
• 在内层循环中，我们需要维护一个集合或者哈希表，用来记录当前子数组 arr[i...j] 中出现了哪些数字。
• 每次加入 INLINECODEdabc5bb0 后，检查集合的大小。如果大小等于 INLINECODE0d6b672a，计数器加 1；如果大小超过了 INLINECODE29d6f115，就可以直接 INLINECODE9f5e3a1e 掉内层循环了（因为继续扩展只会让元素种类更多）。

代码实现（Python）

def subarrays_with_k_distinct_brute_force(arr, K):
    count = 0
    n = len(arr)
    
    # 遍历所有可能的子数组起点
    for i in range(n):
        distinct_elements = set()
        # 遍历所有可能的子数组终点
        for j in range(i, n):
            distinct_elements.add(arr[j])
            
            if len(distinct_elements) == K:
                count += 1
            elif len(distinct_elements) > K:
                # 只要不同元素个数超过了 K，
                # 以 arr[i] 开头的更长的子数组肯定也不符合要求
                break
                
    return count

# 测试一下
arr1 = [2, 1, 2, 1, 6]
print(f"示例 1 结果: {subarrays_with_k_distinct_brute_force(arr1, 2)}") # 输出 7

复杂度分析

• 时间复杂度：O(N^2)。最坏情况下（比如 K 很大），我们需要检查所有 O(N^2) 个子数组。虽然 break 语句能带来常数级的优化，但无法改变量级的本质。
• 空间复杂度：O(N)。哈希集合最多可能存储 N 个元素。

当数组长度达到 10^5 时，这种方法的执行时间将达到百亿量级，显然会在在线判题系统（OJ）中超时。我们需要寻找一种线性的解决方案。

进阶思路：滑动窗口

在处理子数组/子串问题时，滑动窗口 是一把利剑。它通常能将时间复杂度从 O(N^2) 降低到 O(N)。

核心难点与转化

这道题的难点在于要求“恰好 K 个”。

如果我们维护一个窗口，要求窗口内的不同元素个数 不超过 K 个（即 <= K），操作起来会非常顺手：

• 右指针 right 向右移动，扩大窗口，增加元素。
• 如果窗口内不同元素超过 K 个，左指针 left 向右移动，缩小窗口，直到满足条件。

但是，“恰好 K 个”意味着既不能小于 K，也不能大于 K。这使得窗口的伸缩逻辑变得非常复杂：当窗口内元素少于 K 时，我们无法直接盲目地移动左指针，因为我们不知道到底该移动多少才能凑够 K 个。

聪明的解法是利用数学上的包含排除原理。

我们可以定义一个辅助函数 atMostK(arr, K)，它的作用是计算最多包含 K 个不同元素的子数组数量。

那么，答案就是：

atMostK(K) - atMostK(K - 1)
为什么？

• atMostK(K) 包含了：0 个、1 个、…、K 个不同元素的子数组。
• atMostK(K - 1) 包含了：0 个、1 个、…、K-1 个不同元素的子数组。
• 两者相减，0 到 K-1 的部分都被抵消了，剩下的正好就是 恰好 K 个 不同元素的子数组数量！

现在，问题转化为：如何高效实现 atMostK(arr, K)？

实现 atMostK 详解

atMostK 的逻辑是标准的滑动窗口：

• 初始化 INLINECODE47c76992, INLINECODEb5f91d0e, 一个哈希表 freq_map 用于记录频率。
• 遍历 right 从 0 到 n-1：

* 将 INLINECODEd302d3a4 加入 INLINECODE63a2b032。

* 检查：如果 freq_map 的大小（即不同元素个数）超过了 K：

* 移动 INLINECODE13b2ae2e 指针向右，同时减少 INLINECODE33744bb6 中对应元素的频率。

* 如果频率减为 0，从 freq_map 中删除该键。

* 重复此步骤直到 freq_map 大小 <= K。

* 统计：此时，窗口 INLINECODE906b5c24 是满足条件（<= K）的最大窗口。在这个窗口内，以 INLINECODE7540712e 结尾的合法子数组数量是多少？

* 答案是 right - left + 1。

* 解释：这些子数组的起点可以是 INLINECODE888347f9, INLINECODEe6011958, …, INLINECODEeb7b6121。只要起点在 INLINECODEcdb1e69e 之间，加上终点 right，其元素种类必然是窗口种类（<= K）的子集，因此也一定 <= K。

优化后的完整代码

def subarrays_with_k_distinct_optimized(arr, K):
    # 辅助函数：计算最多包含 K 个不同元素的子数组数量
    def at_most_k(k):
        if k  k:
                left_val = arr[left]
                freq_map[left_val] -= 1
                if freq_map[left_val] == 0:
                    del freq_map[left_val]
                left += 1
            
            # 3. 统计以 right 结尾的合法子数组数量
            # 窗口 [left, right] 内的所有元素作为起点都是合法的
            count += right - left + 1
            
        return count

    # 核心公式：恰好 K 个 = (最多 K 个) - (最多 K-1 个)
    return at_most_k(K) - at_most_k(K - 1)

# --- 测试用例 ---
if __name__ == "__main__":
    # 示例 1
    arr1 = [2, 1, 2, 1, 6]
    k1 = 2
    print(f"输入: arr={arr1}, K={k1}")
    print(f"输出: {subarrays_with_k_distinct_optimized(arr1, k1)}") # 期望 7
    
    print("-" * 20)
    
    # 示例 2
    arr2 = [1, 2, 3, 4, 5]
    k2 = 1
    print(f"输入: arr={arr2}, K={k2}")
    print(f"输出: {subarrays_with_k_distinct_optimized(arr2, k2)}") # 期望 5
    
    print("-" * 20)
    
    # 示例 3: 包含重复元素的情况
    arr3 = [1, 1, 1, 1]
    k3 = 1
    print(f"输入: arr={arr3}, K={k3}")
    # 所有子数组都是 [1], [1,1], ... 共 4+3+2+1 = 10 个
    print(f"输出: {subarrays_with_k_distinct_optimized(arr3, k3)}") # 期望 10

复杂度再分析

• 时间复杂度：O(N)。

* 我们在 INLINECODE5c59da49 中遍历了数组一次，INLINECODEc15c6adb 指针只向前走。

* INLINECODE8c174106 指针虽然在内层 INLINECODEa767c3a4 循环中，但因为它最多只能从 0 走到 N，所以总的操作次数也是 O(N)。

我们调用了两次 at_most_k，所以总时间是 2 O(N)，即 O(N)。

* 哈希表的插入、删除、查询操作平均都是 O(1)。

• 空间复杂度：O(K)。

* 哈希表 freq_map 中存储的键值对数量，最多也就是 K+1 个（触发收缩前），所以空间占用与 K 成正比。

常见错误与最佳实践

在实现这个算法时，你可能会遇到一些坑。作为经验丰富的开发者，我要提醒你注意以下几点：

1. 整数溢出

虽然在 Python 中整数大小不受限，但在 Java 或 C++ 中，如果数组长度很大（例如 10^5），子数组的总数量是非常巨大的（N*(N+1)/2 级别）。务必确保你的计数器变量使用 INLINECODEa4d727e7 (C++) 或 INLINECODE5a37d8e8 (Java) 类型，否则会导致溢出，得到错误的负数答案。

2. atMostK(-1) 的处理

在计算 INLINECODEae4526a3 时，如果输入的 K 是 0，那么我们会调用 INLINECODE06c239c4。虽然题目给定 K 是正整数，但在函数编写时，将 INLINECODE205d6726 写得健壮一些（例如 INLINECODEcd22b81c）是一个非常好的习惯。

3. 混淆“窗口数量”与“符合条件的子数组数量”

在滑动窗口中，窗口 INLINECODE3ded4e50 本身只是一个所有子数组的“超集”。真正的关键在于这一行代码：INLINECODEbf06c8c1。

不要错误地认为只有当前这个 INLINECODEe614c3a5 窗口是一个合法的子数组。只要窗口 INLINECODEcc8dd8b7 合法，那么它内部的每一个以 right 结尾的后缀子数组都是合法的。这是初学者最容易晕的地方。

总结

在这篇文章中，我们不仅解决了“恰好包含 K 个不同整数的子数组”这个问题，更重要的是掌握了一种通用的算法思维模型：

• 转化思维：当“恰好”难以直接处理时，尝试用“至少”或“至多”来表示。恰好 K = 至多 K - 至多 (K-1)。
• 滑动窗口模型：处理连续子数组问题时，优先考虑滑动窗口，它通常能带来 O(N) 的最优解。
• 统计技巧：在计算以 INLINECODEb3b79462 结尾的子数组数量时，利用窗口长度的数学性质 INLINECODE0e8bc3ba 是极其高效的。

这种解题思路不仅适用于这道题，还可以广泛应用于诸如“子数组中不同元素个数小于 K 的个数”、“包含 K 个不同字符的最长子串长度”等变种问题中。希望下次你在面试或刷题遇到这类问题时，能自信地运用滑动窗口解决它！

你可以尝试修改上面的代码，去解决相关的变种问题，比如“找出包含最多 K 个不同元素的最长子串长度”，看看能否举一反三。