题目链接直达

1. 题目描述

给你一个由 正 整数组成的数组 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

2. 分析

核心思路：双指针(滑动窗口)+哈希

分析：

1. 题意转化，完全子数组定义：子数组中 不同 元素的数目等于整个数组不同元素的数目。等价于：子数组包含整个数组的所有元素。

2. 滑动窗口：

   1. 固定左端点找到包含所有元素的最小窗口。比如长度为10的数组arr，如果arr[1:8]包含数组所有元素，那么，arr[1:9], arr[1:10] 一定包含数组所有元素。子集的关系。

   2. 移动左端点，找下一个满足的最小窗口。

   3. 反复1，2，更新答案。

3. 代码

值域在[1,2000]，我习惯于直接申请数组代替哈希表，优点在于：无需调用hash函数计算hash，无需hash表扩容时间消耗。

func countCompleteSubarrays(nums []int) int {
	n := len(nums)
	// 首先，先遍历一遍元素，获取不同元素个数
	// 值域数组
	exist := [2001]bool{}
	objCnt := 0
	for _, v := range nums {
		if exist[v] {
			continue
		}
		exist[v] = true
		objCnt++
	}
	// 双指针加hash记录
	bitNums := [2001]int{}
	l, r := -1, -1
	cnt := 0
	ans := 0
	for {
		if r == n {
			break
		}
		for cnt < objCnt {
			r++
			if r == n {
				break
			}
			if bitNums[nums[r]] == 0 {
				cnt++
			}
			bitNums[nums[r]]++
		}
		// 当前答案符合，更新答案，并且移动左指针
		for cnt == objCnt {
			ans += n - r
			if l == r {
				break
			}
			l++
			// 更新左指针
			bitNums[nums[l]]--
			if bitNums[nums[l]] == 0 {
				cnt--
			}
		}
	}
	return ans
}