经典的滑动窗口的题目 力扣 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,即满足条件的子数组的总数。


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


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


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


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


相关文章
|
4月前
|
Web App开发 缓存 前端开发
浏览器常见面试题目及详细答案解析
本文围绕浏览器常见面试题及答案展开,深入解析浏览器组成、内核、渲染机制与缓存等核心知识点。内容涵盖浏览器的主要组成部分(如用户界面、呈现引擎、JavaScript解释器等)、主流浏览器内核及其特点、从输入URL到页面呈现的全过程,以及CSS加载对渲染的影响等。结合实际应用场景,帮助读者全面掌握浏览器工作原理,为前端开发和面试提供扎实的知识储备。
185 4
|
4月前
|
缓存 NoSQL Java
Java Redis 面试题集锦 常见高频面试题目及解析
本文总结了Redis在Java中的核心面试题,包括数据类型操作、单线程高性能原理、键过期策略及分布式锁实现等关键内容。通过Jedis代码示例展示了String、List等数据类型的操作方法,讲解了惰性删除和定期删除相结合的过期策略,并提供了Spring Boot配置Redis过期时间的方案。文章还探讨了缓存穿透、雪崩等问题解决方案,以及基于Redis的分布式锁实现,帮助开发者全面掌握Redis在Java应用中的实践要点。
226 6
|
4月前
|
算法 Java 关系型数据库
校招 Java 面试基础题目解析及学习指南含新技术实操要点
本指南聚焦校招Java面试,涵盖Java 8+新特性、多线程与并发、集合与泛型改进及实操项目。内容包括Lambda表达式、Stream API、Optional类、CompletableFuture异步编程、ReentrantLock与Condition、局部变量类型推断(var)、文本块、模块化系统等。通过在线书店系统项目,实践Java核心技术,如书籍管理、用户管理和订单管理,结合Lambda、Stream、CompletableFuture等特性。附带资源链接,助你掌握最新技术,应对面试挑战。
97 2
|
4月前
|
安全 Java 编译器
Java 校招面试题目合集及答案 120 道详解
这份资料汇总了120道Java校招面试题目及其详细答案,涵盖Java基础、JVM原理、多线程、数据类型、方法重载与覆盖等多个核心知识点。通过实例代码解析,帮助求职者深入理解Java编程精髓,为校招面试做好充分准备。无论是初学者还是进阶开发者,都能从中受益,提升技术实力和面试成功率。附带的资源链接提供了更多学习材料,助力高效备考。
195 3
|
4月前
|
存储 算法 Java
校招 java 面试基础题目及解析
本文围绕Java校招面试基础题目展开,涵盖平台无关性、面向对象特性(封装、继承、多态)、数据类型、关键字(static、final)、方法相关(重载与覆盖)、流程控制语句、数组与集合、异常处理等核心知识点。通过概念阐述和代码示例,帮助求职者深入理解并掌握Java基础知识,为校招面试做好充分准备。文末还提供了专项练习建议及资源链接,助力提升实战能力。
131 0
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
108 1
|
缓存 关系型数据库 MySQL
面试题目总结
面试题目总结
301 6
|
Java C++ Python
【面试宝典】深入Python高级:直戳痛点的题目演示(下)
【面试宝典】深入Python高级:直戳痛点的题目演示(下)
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
109 0
|
设计模式 Unix Python
【面试宝典】深入Python高级:直戳痛点的题目演示(上)
【面试宝典】深入Python高级:直戳痛点的题目演示(上)
下一篇
oss教程