经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)

简介: 经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)

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


  1. ans=0:初始化一个变量ans,用于存储最终结果,即满足条件的子数组的总数。


  1. a=[0]*20000:初始化一个长度为20000的数组a,用于记录每个数字在当前窗口中出现的次数。


  1. left=0:初始化左指针left,用于表示当前窗口的左边界。


  1. norep=len(set(nums)):通过set(nums)来获得数组nums中不重复元素的个数,并将其赋值给norep,表示不重复元素的数量。


  1. m=0:初始化变量m,用于记录当前窗口中出现的新元素的次数。


  1. for right in range(len(nums))::遍历数组nums中的每个元素,right表示当前窗口的右边界。


  1. a[nums[right]]+=1:将当前元素nums[right]在数组a中的计数加1。


  1. if a[nums[right]]==1::如果当前元素nums[right]在当前窗口中第一次出现,则将新元素的数量m加1。


  1. while m==norep::当当前窗口中的新元素数量等于不重复元素的总数时,执行下面的操作。


  1. ans+=len(nums)-right:将当前满足条件的子数组的数量累加到结果ans中。这里使用len(nums)-right来计算当前窗口中满足条件的子数组的个数。


  1. a[nums[left]]-=1:将左边界元素在数组a中的计数减1。


  1. if a[nums[left]]==0::如果左边界元素在当前窗口中消失,即计数为0,则将m减1,表示新元素数量减少了一个。


  1. left+=1:将左指针向右移动,缩小窗口。


  1. 最后输出ans,即满足条件的子数组的总数。


主要目的是计算数组中所有满足特定条件的子数组的总数。具体来说,它通过维护一个滑动窗口,不断调整窗口的左右边界,来统计满足条件的子数组的数量。


该条件是:子数组中包含的不同元素的数量等于整个数组中不同元素的数量。


通过遍历数组,并在遍历过程中维护窗口,当窗口中包含的不同元素数量等于整个数组中不同元素的数量时,就计算当前窗口中满足条件的子数组的数量,并累加到结果中。最终,输出结果即为满足条件的子数组的总数。


这种算法的思想是利用滑动窗口来遍历所有可能的子数组,并在满足条件时进行统计,以提高效率。


相关文章
|
2月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
9天前
|
缓存 关系型数据库 MySQL
面试题目总结
面试题目总结
36 6
|
1天前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
10 0
|
2月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
2月前
|
C语言
【Amazon 面试题1】一个数组,里面得数出现的次数是偶数次,只有一个数出现的次数是奇数次,找出那个出现奇数次的数
本文介绍了解决Amazon面试题的一种方法,即在一个所有数字出现次数都是偶数,除了一个数字出现奇数次的数组中,利用异或运算的性质找出出现奇数次的数字,并提供了C语言实现的代码示例。
49 1
|
2月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
2月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组
|
11天前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
46 6