2537-统计好子数组的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个整数数组 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 <= 105
  • 1 <= nums[i], k <= 109

子数组统计问题，常用双指针（不定长滑动窗口）实现，具体原理可以看我的【同向双指针+简洁模板】 ，看完你就掌握双指针啦~

本题的做法：

用一个哈希表 cnt 统计窗口内每个元素的出现次数。

枚举子数组右端点 right，那么答案增加了 cnt}[\textit{nums}[\textit{right}]]；然后看左端点 left 最大可以是多少，如果去掉左端点，答案没有小于 k，就可以移动左端点。

由于左端点及其左边的都可以是好子数组的左端点，所以每个右端点对应的答案个数为 left}+1。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        cnt = Counter()
        ans = left = pairs = 0
        for x in nums:
            pairs += cnt[x]
            cnt[x] += 1  # 移入右端点
            while pairs - cnt[nums[left]] + 1 >= k:
                cnt[nums[left]] -= 1  # 移出左端点
                pairs -= cnt[nums[left]]
                left += 1
            if pairs >= k:
                ans += left + 1
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public long countGood(int[] nums, int k) {
        var cnt = new HashMap<Integer, Integer>();
        long ans = 0;
        int left = 0, pairs = 0;
        for (int x : nums) {
            pairs += cnt.getOrDefault(x, 0);
            cnt.merge(x, 1, Integer::sum); // 移入右端点
            while (pairs - cnt.get(nums[left]) + 1 >= k)
                pairs -= cnt.merge(nums[left++], -1, Integer::sum); // 移出左端点
            if (pairs >= k) ans += left + 1;
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    long long countGood(vector<int> &nums, int k) {
        unordered_map<int, int> cnt;
        long ans = 0;
        int left = 0, pairs = 0;
        for (int x : nums) {
            pairs += cnt[x]++; // 移入右端点
            while (pairs - cnt[nums[left]] + 1 >= k)
                pairs -= --cnt[nums[left++]]; // 移出左端点
            if (pairs >= k) ans += left + 1;
        }
        return ans;
    }
};
[sol1-Go]
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
34
35
36
37
38
func countGood(nums []int, k int) (ans int64) {
	cnt := map[int]int{}
	left, pairs := 0, 0
	for _, x := range nums {
		pairs += cnt[x]
		cnt[x]++ // 移入右端点
		for pairs-cnt[nums[left]]+1 >= k {
			cnt[nums[left]]-- // 移出左端点
			pairs -= cnt[nums[left]]
			left++
		}
		if pairs >= k {
			ans += int64(left + 1)
		}
	}
	return
}
````

还可以把更新 ans 的逻辑写在循环内部。

你更喜欢哪种写法呢？

```py [sol2-Python3]
class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        cnt = Counter()
        ans = left = pairs = 0
        for x in nums:
            pairs += cnt[x]
            cnt[x] += 1  # 移入右端点
            ans += left
            while pairs >= k:
                ans += 1
                cnt[nums[left]] -= 1  # 移出左端点
                pairs -= cnt[nums[left]]
                left += 1
        return ans
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public long countGood(int[] nums, int k) {
        var cnt = new HashMap<Integer, Integer>();
        long ans = 0;
        int left = 0, pairs = 0;
        for (int x : nums) {
            pairs += cnt.getOrDefault(x, 0);
            cnt.merge(x, 1, Integer::sum); // 移入右端点
            ans += left;
            while (pairs >= k) {
                pairs -= cnt.merge(nums[left++], -1, Integer::sum); // 移出左端点
                ++ans;
            }
        }
        return ans;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long countGood(vector<int> &nums, int k) {
        unordered_map<int, int> cnt;
        long ans = 0;
        int left = 0, pairs = 0;
        for (int x : nums) {
            pairs += cnt[x]++; // 移入右端点
            ans += left;
            while (pairs >= k) {
                pairs -= --cnt[nums[left++]]; // 移出左端点
                ++ans;
            }
        }
        return ans;
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func countGood(nums []int, k int) (ans int64) {
	cnt := map[int]int{}
	left, pairs := 0, 0
	for _, x := range nums {
		pairs += cnt[x]
		cnt[x]++ // 移入右端点
		ans += int64(left)
		for pairs >= k {
			ans++
			cnt[nums[left]]-- // 移出左端点
			pairs -= cnt[nums[left]]
			left++
		}
	}
	return
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums 的长度。
  • 空间复杂度：O(n)。

相似题目（同向双指针）

 Comments
On this page
2537-统计好子数组的数目