【Leetcode 每日一题】2799. 统计完全子数组的数目

问题背景

给你一个由 正 整数组成的数组 $nums$。
如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

• 子数组中 不同 元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。
子数组 是数组中的一个连续非空序列。

数据约束

• $1\le nums.length\le 1000$
• $1\le nums[i]\le 2000$

解题过程

子数组越长，包含的元素种类越多，越有可能符合条件，满足单调性的要求，可以滑窗。
累计答案的时候需要注意，整个数组中元素的数目不会小于子数组中元素的数目。
出现某个范围内的元素已经包含了所有种类，这时候扩展端点得到的所有子数组都是符合条件的。
其中，如果在内层循环中进行统计，那么右端点可以选择从当前位置到数组末尾的所有所有位置；如果在内层循环结束时进行统计，那么左端点可以选择从零位置开始到当前位置之前的所有位置。

具体实现

class Solution {public int countCompleteSubarrays(int[] nums) {int[] count = new int[2010];Set<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int diff = set.size();int res = 0;int n = nums.length;for (int left = 0, right = 0; right < n; right++) {if (count[nums[right]]++ == 0) {diff--;}while (diff == 0) {if(--count[nums[left++]] == 0) {diff++;}// 在内层循环中统计答案，固定左端点得到的所有子数组都是符合条件的res += n - right;}// 在内层循环结束时统计答案，固定右端点得到的所有子数组都是符合条件的// res += left;}return res;}
}