点击获取AI摘要

2537. 统计好子数组的数目 M

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。

子数组 是原数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。

示例 2：

输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：

  • [3,1,4,3,2,2] 有 2 对。
  • [3,1,4,3,2,2,4] 有 3 对。
  • [1,4,3,2,2,4] 有 2 对。
  • [4,3,2,2,4] 有 2 对。

提示：

  • 1 <= nums.length <= 10510^5
  • 1 <= nums[i], k <= 10910^9

问题分析

给定一个整数数组 nums 和一个整数 k，要求返回数组中好子数组的数目。题目中“好子数组”的定义为：子数组中存在至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j]，也就是我们需要找出数组中所有满足至少有 k 对下标 (i, j)（其中 i < j 且元素相同）的子数组的数量。

算法思路

  1. 当一个元素 x 在窗口中出现了 c 次时，它贡献的配对数量为组合数 C(c,2)=c(c−1)2C(c,2)=\frac{c(c−1)} 2，但动态调整更高效的方式是通过增量/减量来维护总数。
  2. 使用双指针（滑动窗口）技术来遍历所有连续子数组。
  3. 维护一个窗口 [l, r]，以及窗口中每个数字出现的频数 freq。
  4. 同时在每一步更新窗口内的成对数字数量 count。当我们向窗口中添加新元素 x 时，窗口中原先 x 出现的次数为 freq[x]，那么新增的对数为 freq[x]（每个已有的 x 和新加入的 x 都可以构成一对）。因此更新 count += freq[x]，然后 freq[x] 加 1。
  5. 对于每个左边界 l，利用右指针 r 尽可能扩展窗口，直到 count >= k。设当窗口达到条件时，当前的 r 满足条件，则对于定左边界 l，所有右边界 r' 属于 [r, n-1] 的窗口均满足条件，因此可以直接将 n - r 加入答案。
  6. 随后移动左边界 l，同时更新 count。在移除窗口最左边元素时，假设其值为 x，此时删除该元素会导致窗口中 x 的出现次数减少，进而需要减少的对数为 freq[x] - 1（因为该 x 和其它 x 形成的对数就少了）。

时间复杂度

每个元素最多被右指针和左指针访问（加入和移除窗口）各一次，因此双指针方法整体时间复杂度为 O(n)O(n)，其中 n 是数组的长度。

代码分解

窗口扩展：
对于每个窗口左边界 l，通过右指针 r向右扩展窗口，直到窗口内满足 count >= k。在扩展过程中使用频次统计更新 count。

直接计数：
一旦找到最小的右边界 r 使得 [l, r] 满足条件，则所有 [l, r], [l, r+1], …, [l, n-1] 的子数组也均满足条件，因此可以直接加上 n - r。

滑动窗口收缩：
移动左边界 l时，需要将 nums[l] 从窗口中移除，同时调整 freq 和 count。移除时由于原先 x 出现次数为 freq[x]，其对对数贡献为 freq[x] - 1（移除后剩余的配对数为 freq[x] - 1，因此减少 freq[x] - 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
from collections import defaultdict

class Solution:
    def countGood(self, nums, k: int) -> int:
        n = len(nums)
        # 字典存储每个数字的频次
        freq = {}
        count = 0  # 当前窗口中满足条件的对数数量
        res = 0    # 结果计数
        r = 0
        
        # 遍历左边界
        for l in range(n):
            # 不断扩展右边界，使窗口对数数量至少为 k
            while r < n and count < k:
                x = nums[r]
                # 在添加前，x已有 freq.get(x, 0) 次，新增的对数即为这个频次
                count += freq.get(x, 0)
                freq[x] = freq.get(x, 0) + 1
                r += 1
            
            # 如果当前窗口 [l, r-1] 的配对数量至少为 k，则右边所有扩展窗口都满足条件
            if count >= k:
                res += (n - r + 1)
            
            # 在将 l 右移前需要移除 nums[l] 对 count 的贡献
            x = nums[l]
            freq[x] -= 1
            # 当移除一个 x 时，其对配对数的贡献为移除前该 x 与其它相同元素之间的对数数目，即 freq[x]（因为移除后，剩余的 x 数量为 freq[x]）
            count -= freq[x]
            
        return res