给你一个由 正 整数组成的数组 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 。
使用滑动窗口来解决 ,定义一个a[20000],数组的大小可以参考具体数据的范围。
重点是理解ans=len(nums)-right.举一个简单的例子
代码如下:
ans=0
a=[0]*20000
left=0
norep=len(set(nums))
m=0#定义出现新元素的次数
for right in range(len(nums)):
a[nums[right]]+=1
if a[nums[right]]==1:
m+=1
while m==norep:
ans+=len(nums)-right
a[nums[left]]-=1
if a[nums[left]]==0:#说明消失了一个新元素,就不满足条件了
m-=1
left+=1
print(ans)
-
ans=0
:初始化一个变量ans
,用于存储最终结果,即满足条件的子数组的总数。 -
a=[0]*20000
:初始化一个长度为20000的数组a
,用于记录每个数字在当前窗口中出现的次数。 -
left=0
:初始化左指针left
,用于表示当前窗口的左边界。 -
norep=len(set(nums))
:通过set(nums)
来获得数组nums
中不重复元素的个数,并将其赋值给norep
,表示不重复元素的数量。 -
m=0
:初始化变量m
,用于记录当前窗口中出现的新元素的次数。 -
for right in range(len(nums)):
:遍历数组nums
中的每个元素,right
表示当前窗口的右边界。 -
a[nums[right]]+=1
:将当前元素nums[right]
在数组a
中的计数加1。 -
if a[nums[right]]==1:
:如果当前元素nums[right]
在当前窗口中第一次出现,则将新元素的数量m
加1。 -
while m==norep:
:当当前窗口中的新元素数量等于不重复元素的总数时,执行下面的操作。 -
ans+=len(nums)-right
:将当前满足条件的子数组的数量累加到结果ans
中。这里使用len(nums)-right
来计算当前窗口中满足条件的子数组的个数。 -
a[nums[left]]-=1
:将左边界元素在数组a
中的计数减1。 -
if a[nums[left]]==0:
:如果左边界元素在当前窗口中消失,即计数为0,则将m
减1,表示新元素数量减少了一个。 -
left+=1
:将左指针向右移动,缩小窗口。 -
最后输出
ans
,即满足条件的子数组的总数。
主要目的是计算数组中所有满足特定条件的子数组的总数。具体来说,它通过维护一个滑动窗口,不断调整窗口的左右边界,来统计满足条件的子数组的数量。
该条件是:子数组中包含的不同元素的数量等于整个数组中不同元素的数量。
通过遍历数组,并在遍历过程中维护窗口,当窗口中包含的不同元素数量等于整个数组中不同元素的数量时,就计算当前窗口中满足条件的子数组的数量,并累加到结果中。最终,输出结果即为满足条件的子数组的总数。
这种算法的思想是利用滑动窗口来遍历所有可能的子数组,并在满足条件时进行统计,以提高效率。