[LeetCode] 每日一题 2537. 统计好子数组的数目（滑动窗口）

题目描述

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

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

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

题目链接

https://leetcode.cn/problems/count-the-number-of-good-subarrays/description

示例输入

示例 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 <= 10^5

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

解题思路

这题相比前几天的题目来说，难度算是中规中矩的，属于典型的滑动窗口应用场景。题目要求我们统计所有好子数组的数量，其中“好子数组”被定义为包含至少 k 对 (i, j)，且 arr[i] == arr[j] 且 i < j 的子数组。

直观上，我们可以枚举所有子数组，暴力判断是否满足条件，但这样时间复杂度会非常高，显然不可取。因此，我采用了更高效的滑动窗口解法：

• 我们固定滑动窗口的右端点，向右扩展；

• 用一个 HashMap 维护窗口中每个数字出现的频次，同时计算出当前窗口中满足条件的对数；

• 当对数大于等于 k 时，说明以当前右端点为结束的所有左端点在 [0, left] 范围内都可以构成“好子数组”；

• 然后我们向右滑动左端点，直到窗口中的对数再次小于 k，继续向右扩展右端点。

这个过程保证了每一个滑动窗口都只遍历了一遍，性能非常优秀。

代码实现

class Solution {
    public long countGood(int[] nums, int k) {
        HashMap<Integer, Integer> count = new HashMap<>();
        long ans = 0;
        int temp = 0;
        int left = 0;
        for (int num : nums) {
            int cnt = count.getOrDefault(num, 0);
            temp += cnt;
            count.put(num, cnt + 1);
            while (temp >= k) {
                num = nums[left];
                cnt = count.get(num);
                temp -= (cnt - 1);
                count.put(num, cnt - 1);
                left++;
            }
            ans += left;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，每个元素最多被加入和移除一次

• 空间复杂度：O(n)，用于记录窗口内元素频次的 HashMap

整体效率还是很优秀的，滑窗配上哈希表频次统计组合拳 💪

总结

这题是滑动窗口的一个变种，关键在于如何用合理的数据结构（如 Map）实时维护窗口内的数据状态。整道题的本质其实是在维护一个“对数”的数量，在满足条件的情况下尽可能多地扩展左端点，从而统计满足条件的子数组数量。这类题型练得越多，对滑窗的掌握也会更灵活，值得反复练习 ✅

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。