点击获取AI摘要

2799. 统计完全子数组的数目 M

给你一个由 正 整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

  • 子数组中 不同 元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

示例 1：

输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。

示例 2：

输入：nums = [5,5,5,5]
输出：10
解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2000

问题分析

  • 给定正整数数组 nums，长度为 n（≤1000\le 1000）。

  • 记数组 nums 中 不同 元素的总数为 KK。

  • 我们需要统计「子数组中不同元素数 等于KK」的子数组个数。

算法思路

暴力枚举：枚举左端点 i (0⋯n−1)i\text{ }(0\cdots n-1) ，再枚举右端点 j (i⋯n−1)j\text{ }(i\cdots n-1)，对每个子数组 nums[i:j+1] 用哈希或 set 统计不同元素数，再对比是否等于 KK。

时间复杂度：

  • 枚举子数组一共 O(n2)O(n^2)
  • 每个子数组去重也要 O(n)O(n)
  • 合计 O(n3)O(n^3)，在 n=1000n=1000 时是不可行的（10910^9 级别的操作）。

暴力+优化也可通过测试：采用双重循环遍历所有可能的子数组，并检查每个子数组是否符合条件，对于每一个起始索引 i，逐步扩展结束索引 j，使用集合记录当前子数组中的元素。一旦集合大小达到整个数组的不同元素数量，则计数加一；若超过该数量则提前终止内层循环，时间复杂度最坏为O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        total_unique = len(set(nums))
        if total_unique == 0:
            return 0
        
        K = total_unique
        result = 0
        n = len(nums)
        
        for i in range(n):
            current_set = set()
            for j in range(i, n):
                current_set.add(nums[j])
                if len(current_set) == K:
                    result += 1
                elif len(current_set) > K:
                    break  # 一旦超出所需的唯一计数，就不需要检查其他元素
        return result

我们令函数

F(k)=“不同元素数≤k”的子数组数量.F(k) = \text{“不同元素数} \leq k \text{”的子数组数量}.

则恰好等于 KK 的子数组数目

#{distinct=K}=F(K)−F(K−1).\#\{\text{distinct} = K\} = F(K) - F(K - 1).

所有「不同数 ≤K\le K」的子数组共 F(K)F(K) 个，

但其中也包括「不同数 ≤K−1\le K−1」的 F(K−1)F(K-1) 个，

二者相减，即剩下「不同数恰好 = KK」的部分。

使用滑动窗口 + 双指针：

  1. 窗口定义
    • 左指针 i，右指针 j，初始都指向 0。
    • 窗口 nums[i…j] 内维护哈希表 count，记录每个数字出现的次数。
    • 变量 distinct 表示当前窗口内 不同 元素的个数。
  2. 右指针扩展
    • 遍历 j 从 0 到 n−1n-1：
      • 将 nums[j] 加入窗口：若原来 count[nums[j]]==0，则 distinct += 1；再 count[nums[j]] += 1。
  3. 左指针收缩
    • 当 distinct > k 时，需要不断移动左指针 i：
      • 从窗口移出 nums[i]：count[nums[i]] -= 1；若 count[nums[i]] 变为 0，则 distinct -= 1；然后 i += 1
    • 收缩后，窗口再次保证 distinct ≤ k。
  4. 计数子数组
    • 对于每一个新的 j 位置，当前窗口 所包含的所有合法子数组（以 j 为右端）数量就是窗口长度：j - i + 1。
      • 因为任意左端点 LL 满足 i≤L≤ji \le L \le j，子数组 nums[L…j] 都有 distinct ≤ k。
  5. 累加结果
    • 对每个 j，将 j - i + 1 累加到 res，最终 res = F(k)。

以 nums = [1,3,1,2,2]，k=2k=2 为例，计算「不同数 ≤2\le 2」的子数组数：

步骤 j 加入 nums[j] window distinct i 新增子数组数 j−i+1 累计 res
初始化 — — [] 0 0 — 0
1 0 1 [1] 1 0 0−0+1 = 1 1
2 1 3 [1,3] 2 0 1−0+1 = 2 3
3 2 1 [1,3,1] 2 0 2−0+1 = 3 6
4 3 2 → distinct=3 [1,3,1,2] → 收缩 → [3,1,2] 2 → 经过收缩 1 3−1+1 = 3 9
5 4 2 [3,1,2,2] 3→收缩→2 2 4−2+1 = 3 12

最终我们得到 F(2) = 12。
类似地可以算出 F(1)，最后 F(2) - F(1) 就是「不同数恰好 =2=2」的子数组数。

时间复杂度

  • 时间复杂度：一次 atMost 为 O(n)O(n)，每个元素最多进出窗口各一次共两次，故 O(n)O(n)
  • 空间复杂度：哈希表存储最多 nn 个键，故 O(n)O(n)

代码分解

  1. 用「≤K\le K」和「≤K−1\le K−1」之差得到「=K=K」。

  2. 滑动窗口维护「不同元素数 ≤k\le k」的区间，通过左右指针一遍扫描完成。

  3. 累加 (j - i + 1) 即可统计当前右端下所有合法子数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def countCompleteSubarrays(self, nums):
        # 整体不同元素个数
        K = len(set(nums))

        # 计算「不同元素 ≤ k」的子数组数量
        def atMost(k):
            count = {}       # 哈希表：元素 -> 频次
            res = 0
            distinct = 0     # 当前窗口中不同元素数
            left = 0         # 窗口左指针
            for right, x in enumerate(nums):
                # 右指针加入
                if count.get(x, 0) == 0:
                    distinct += 1
                count[x] = count.get(x, 0) + 1

                # 如果超过 k，左指针收缩
                while distinct > k:
                    y = nums[left]
                    count[y] -= 1
                    if count[y] == 0:
                        distinct -= 1
                    left += 1

                # 以 right 为结尾的「不同元素 ≤ k」子数组有 (right - left + 1) 个
                res += right - left + 1

            return res

        # 答案 = 至多 K 不同 − 至多 (K-1) 不同
        return atMost(K) - atMost(K - 1)