难度: Medium
给你一个由 正 整数组成的数组 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运行时间: 40 ms
内存: 16.6 MB
class Solution:
def countCompleteSubarrays(self, nums: List[int]) -> int:
target = len(set(nums))
cnt = {}
left = ans = 0
for right, num in enumerate(nums):
if num not in cnt:
cnt[num] = 1
else:
cnt[num] += 1
while len(cnt) == target:
cnt[nums[left]] -= 1
if cnt[nums[left]] == 0:
del cnt[nums[left]]
left += 1
ans += left
return ans
# target = len(set(nums))
# cnt = Counter()
# ans = left = 0
# for right, num in enumerate(nums):
# cnt[num] += 1
# while len(cnt) == target:
# cnt[nums[left]] -= 1
# if cnt[nums[left]] == 0:
# del cnt[nums[left]]
# left += 1
# ans += left
# return ans
# target = len(set(nums))
# cnt = Counter()
# ans = left = 0
# for v in nums:
# cnt[v] += 1
# while len(cnt) == target:
# x = nums[left]
# cnt[x] -= 1
# if cnt[x] == 0:
# del cnt[x]
# left += 1
# ans += left
# return ans
# n = len(nums)
# target = len(set(nums))
# st,end = 0,0
# ans = 0
# while end < n:
# if len(set(nums[st:end+1])) == target:
# ans += n - end
# st += 1
# else:
# end += 1
# return ans
此题解采用滑动窗口的方法来寻找所有的完全子数组。首先，计算整个数组中不同元素的总数作为目标数(target)。使用一个哈希表(cnt)来记录窗口内各元素的出现次数，并动态调整窗口的大小。遍历数组元素，每次右移右边界(right)，将元素加入哈希表。当窗口内不同元素的数量等于目标数时，尝试缩小窗口，即逐步右移左边界(left)，直到窗口内不同元素的数量小于目标数。在每次右移左边界之前，将当前左边界到右边界形成的子数组数量加入结果(ans)，这些子数组都是完全子数组。
时间复杂度: O(n)
空间复杂度: O(u)
class Solution:
def countCompleteSubarrays(self, nums: List[int]) -> int:
target = len(set(nums)) # 计算数组中不同元素的数量
cnt = {} # 哈希表用于记录窗口内各元素的频数
left = ans = 0 # 初始化左边界和结果计数器
for right, num in enumerate(nums): # 遍历数组，同时记录元素的索引和值
if num not in cnt:
cnt[num] = 1 # 如果元素第一次出现，初始化计数为1
else:
cnt[num] += 1 # 否则增加计数
while len(cnt) == target: # 当窗口内不同元素数量等于目标数
cnt[nums[left]] -= 1 # 减少左边界元素的计数
if cnt[nums[left]] == 0:
del cnt[nums[left]] # 如果计数为0，则从哈希表中移除该元素
left += 1 # 右移左边界
ans += left # 累加当前左边界到右边界形成的子数组数量
return ans # 返回结果
在使用滑动窗口方法时，数组中元素的重复性本身并不直接影响窗口的扩展和收缩。窗口的扩展（即增加右边界）是基于加入新元素并更新其计数，而窗口的收缩（即移动左边界）是基于减少左边界元素的计数，并在计数为0时从哈希表中移除该元素。重复元素的存在主要影响的是窗口内元素计数的变化，但滑动窗口的基本逻辑，即扩展直到包含所有不同元素，以及收缩直到不再包含所有不同元素，保持不变。
在缩小窗口的过程中，停止移动左边界的条件是窗口内不同元素的数量小于目标数，因为这表示窗口不再形成一个完全子数组（即不包含所有不同元素）。这一策略足以找到所有完全子数组，因为只有当窗口包含所有不同元素时，它才是一个有效的完全子数组。一旦不满足这一条件，任何进一步的缩小都将使窗口失去其“完全性”。因此，这种策略确保了所有可能的完全子数组都被计算在内。
在滑动窗口中先增加元素计数再判断窗口内元素数量是否等于目标数是为了确保每次窗口的状态更新都是基于最新的数据。这种顺序允许算法在每次迭代时正确地评估窗口是否已经包含了所有不同元素。如果顺序相反，即先判断后更新计数，则可能导致在某些迭代中错过窗口状态的正确评估（例如，可能会错误地认为窗口还未包含所有不同元素）。因此，这种顺序的选择对算法的正确性至关重要，而对效率的影响主要体现在确保每次窗口调整都基于完整且准确的数据，从而避免不必要的重复计算或错误的状态判断。