题目链接直达

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
}