class Solution {
public:
int countCompleteSubarrays(vector<int>& nums) {
}
};
6900. 统计完全子数组的数目
给你一个由 正 整数组成的数组 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原站题解
cpp 解法, 执行用时: 40 ms, 内存消耗: 35.6 MB, 提交时间: 2023-07-31 11:27:31
class Solution {
public:
int countCompleteSubarrays(vector<int> &nums) {
int m = unordered_set<int>(nums.begin(), nums.end()).size();
unordered_map<int, int> cnt;
int ans = 0, left = 0;
for (int v: nums) { // 枚举子数组右端点 v=nums[i]
cnt[v]++;
while (cnt.size() == m) {
int x = nums[left++];
if (--cnt[x] == 0)
cnt.erase(x);
}
ans += left; // 子数组左端点 < left 的都是合法的
}
return ans;
}
};
javascript 解法, 执行用时: 80 ms, 内存消耗: 45.6 MB, 提交时间: 2023-07-31 11:27:16
/**
* @param {number[]} nums
* @return {number}
*/
var countCompleteSubarrays = function (nums) {
const m = new Set(nums).size;
let cnt = new Map();
let ans = 0, left = 0;
for (const v of nums) { // 枚举子数组右端点 v=nums[i]
cnt.set(v, (cnt.get(v) ?? 0) + 1);
while (cnt.size === m) {
const x = nums[left++];
cnt.set(x, cnt.get(x) - 1);
if (cnt.get(x) === 0)
cnt.delete(x);
}
ans += left; // 子数组左端点 < left 的都是合法的
}
return ans;
};
java 解法, 执行用时: 7 ms, 内存消耗: 42.7 MB, 提交时间: 2023-07-31 11:27:00
class Solution {
public int countCompleteSubarrays(int[] nums) {
var set = new HashSet<Integer>();
for (int x : nums) set.add(x);
int m = set.size();
var cnt = new HashMap<Integer, Integer>();
int ans = 0, left = 0;
for (int v : nums) { // 枚举子数组右端点 v=nums[i]
cnt.merge(v, 1, Integer::sum);
while (cnt.size() == m) {
int x = nums[left++];
if (cnt.merge(x, -1, Integer::sum) == 0)
cnt.remove(x);
}
ans += left; // 子数组左端点 < left 的都是合法的
}
return ans;
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 16.2 MB, 提交时间: 2023-07-31 11:22:16
# 经典滑动窗口
class Solution:
def countCompleteSubarrays(self, nums: List[int]) -> int:
m = len(set(nums)) # 唯一元素个数
cnt = Counter()
ans = left = 0
for v in nums: # 枚举子数组右端点 v=nums[i]
cnt[v] += 1
while len(cnt) == m:
x = nums[left]
cnt[x] -= 1
if cnt[x] == 0:
del cnt[x]
left += 1
ans += left # 子数组左端点 < left 的都是合法的
return ans