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. 分析
核心思路:双指针(滑动窗口)+哈希
分析:
题意转化,完全子数组定义:子数组中 不同 元素的数目等于整个数组不同元素的数目。等价于:子数组包含整个数组的所有元素。
滑动窗口:
固定左端点找到包含所有元素的最小窗口。比如长度为10的数组arr,如果arr[1:8]包含数组所有元素,那么,arr[1:9], arr[1:10] 一定包含数组所有元素。子集的关系。
移动左端点,找下一个满足的最小窗口。
反复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
}
评论