LeetCode 每日一题 2799. 统计完全子数组的数目

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 <= 1000
1 <= nums[i] <= 2000

题解

不难注意到，对于完全子数组，子数组越长越合法

又是 子数组 又是 越长越合法

很显然就是用滑动窗口

窗口右边界 r 代表子数组结尾，左边界 l 代表子数组开头

r 不断右移，当子数组满足条件时，l 开始右移，直到第一次不满足条件，那么以 l 左边所有数字为开头的子数组都是合法的，即有 l 个完全子数组，res+=l，之后 r 接着右移，即使右移之后窗口内的子数组仍然不满足条件，只是 l 不动而已，还是有 l 个满足条件的子数组，res+=l

r 不断右移，即枚举出所有子数组的结尾，遍历完数组就是所有的完全子数组

代码如下↓

class Solution {
public:int countCompleteSubarrays(vector<int>& nums) {set<int> s;unordered_map<int,int> arr;for(int i:nums){s.insert(i);}int n=s.size();int sum=0;int l=0;int r=n-1;for(int i=0;i<=r;i++){if(arr[nums[i]]++==0){sum++;}}long long res=0;while(r<nums.size()){while(sum==n){if(--arr[nums[l]]==0){sum--;}l++;}res+=l;r++;if(r>=nums.size()){break;}if(arr[nums[r]]++==0){sum++;}}return res;}
};