目标
给你一个由 正 整数组成的数组 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 <= 1000
- 1 <= nums[i] <= 2000
思路
求数组的完全子数组数目，完全子数组指包含数组中的所有不同元素的子数组。
使用哈希集合统计数组中的不同元素个数，使用滑动窗口统计符合条件的子数组数目。初始化时，记录窗口内元素的出现次数，直到包含所有不同元素。循环内如果缺少元素种类则扩展右边界，然后收缩左边界，直到移出元素的出现次数降为 0。
代码
/**
* @date 2025-04-24 0:53
*/
public class CountCompleteSubarrays2799 {
public int countCompleteSubarrays(int[] nums) {
Set<Integer> set = new HashSet<>();
int max = 0;
for (int num : nums) {
set.add(num);
max = Math.max(max, num);
}
int kinds = set.size();
int left = 0, right = 0;
set.clear();
int[] cnt = new int[max + 1];
while (set.size() < kinds) {
cnt[nums[right]]++;
set.add(nums[right++]);
}
int n = nums.length;
int res = 0;
int out = nums[left];
do {
while (right < n && cnt[out] == 0) {
cnt[nums[right++]]++;
}
while (left < n && cnt[out] > 0) {
res += n - right + 1;
out = nums[left];
cnt[nums[left++]]--;
}
} while (right < n);
return res;
}
}
性能
