[LeetCode] 每日一题 2799. 统计完全子数组的数目（滑动窗口）
题目描述
给你一个由 正 整数组成的数组 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 <= 10001 <= nums[i] <= 2000
解题思路
这道题是一个非常经典的 滑动窗口 应用题，目标是找出所有“完全子数组”，即其中包含了整个数组中所有不同元素的子数组个数。
我的整体思路是：
首先统计整个数组中一共有多少个不同的元素（我们可以称之为“全局唯一元素数目”）。
然后通过一个右端点不断右移的滑动窗口进行遍历，并在每次满足窗口中元素种类数达到“全局唯一元素数目”这个“稳态”时：
不断移动左端点，直到跳出稳态。
在这个过程中，每一个可能的左端点都对应一个完全子数组，因为在这些位置向右扩展都满足条件。
关键点在于，当右端点固定时，左端点向左滑动到第一个不满足条件的位置之间的所有子数组，都是合法的。
整个过程保持了一个窗口的滑动，并且在窗口进入“稳态”后，我们进行贡献统计，再滑动左端以跳出当前稳态，寻找下一个合法区间。
这种写法兼顾了效率和易于理解，核心思想就是“稳态时统计贡献，失稳时滑动窗口”。
代码实现
class Solution {
public int countCompleteSubarrays(int[] nums) {
int ans = 0;
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int n = set.size();
HashMap<Integer, Integer> count = new HashMap<>(n);
int left = 0;
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
while (count.size() == n) {
count.put(nums[left], count.get(nums[left]) - 1);
if (count.get(nums[left]) == 0) {
count.remove(nums[left]);
}
left++;
}
ans += left;
}
return ans;
}
}复杂度分析
时间复杂度：O(n)
每个元素最多被左指针和右指针各访问一次，总体是线性的
空间复杂度：O(n)
使用了两个哈希结构：一个用于统计全局唯一数，一个用于维护当前窗口内的数字计数
总结
今天这题对滑动窗口的稳态操作要求较高，是一道适合熟悉窗口左边界如何变化的好题。特别注意的是，每次我们在找到稳态时，就可以通过统计左端点前移的所有情况来一次性增加多个子数组贡献，而不是一个一个枚举，提高了效率。
实战中类似的“窗口内种类数与目标种类数匹配”的问题都可以套用这个思路，值得反复练习和体会！
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。