统计好子数组的数目

发表于 更新于 分类于

    6293. 统计好子数组的数目

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

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

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

    示例 1：

    ```txt

    输入：nums = [1,1,1,1,1], k = 10

    输出：1

    解释：唯一的好子数组是这个数组本身。

    ```

    示例 2：

    ```txt

    输入：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 <= 10^5

    • 1 <= nums[i], k <= 10^9

题目

6293. 统计好子数组的数目

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

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

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

示例 1：

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

示例 2：

1
2
3
4
5
6
7
输入：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 <= 10^5
  • 1 <= nums[i], k <= 10^9

题解

方法一：

思路

滑动窗口

维护窗口[l,r]内的满足arr[i] ==arr[j]的下标对(i,j)的个数cnt恰好小于k。此时在[0, l-1]中任意数为开头，r结束的子数组均为好子数组。

我们需要一个哈希表mp统计窗口内每个数i出现了多少次mp[i]。
在r增长前，区间内nums[r]的个数就是cnt增长的个数。
在l增长后，区间内nums[l]的个数就是cnt减少的个数。

算法过程

r不断增长，对于每个r，窗口[l,r]内cnt若不小于k则不断让l增长，当cnt小于k时，累加以r作为结尾的合法子数组个数l。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    using ll = long long;
    long long countGood(vector<int>& nums, int k) {
        map<int,ll> mp;
        ll cnt = 0, ans = 0;
        for (int r=0, l=0; r<nums.size(); r++) {
            cnt += mp[nums[r]]++;
            while (cnt >= k) {
                cnt -= --mp[nums[l]];
                l++;
            }
            //[0,l)区间元素个数l
            ans += l;
        }
        return ans;
    }
};