经典的滑动窗口的题目 力扣 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,用于存储最终结果,即满足条件的子数组的总数。

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/671662.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【1】AI介绍

迎接 AGI 时代 AGI(Artificial General Intelligence),人工通用智能,AGI是一种可以执行复杂任务的人工智能,能够完全模仿人类智能的行为。应用领域涉及医疗、交通、智能家居等多个与人类活动密切相关的领域。 AGI 多久会到来? 乐观预测:明年(未来已来)主流预测:3-5…

【云原生】Docker Compose 使用详解

目录 一、前言 二、Docker Compose 介绍 2.1 Docker Compose概述 2.2 Docker Compose特点 2.3 Docker Compose使用场景 三、Docker Compose 搭建 3.1 安装docker环境 3.2 Docker Compose安装方式一 3.2.1 下载最新版/如果不是最新可替换最新版本 3.2.2 设置权限 3.2.…

Zigbee +PC上位机 无线控制二维云台开发笔记

今日尝试开发一款简单好学的PC上位机无线控制二维云台的小试验品: 主要开发环境与工具介绍: 单片机 STM32F103C8T6 使用标准库函数编程 Visual Studio 2022软件C# Winform 开发 上位机控制软件 DL_20 无线串口模块 + USB-TTL 模块 实现无线通…

使用 Scapy 库编写 Ping of Death 攻击脚本

一、介绍 1.1 概述 Ping of Death(PoD)攻击是一种历史悠久的拒绝服务(DoS)攻击,攻击者通过发送特制的畸形ICMP Echo请求数据包,导致目标系统无法正确处理,从而导致系统崩溃、重启或无法响应正…

用于相似图片搜索引擎的Python OpenCV图像直方图

图像直方图 那么,图像直方图到底是什么? 图片 图像的构成是由像素点构成的,每个像素点的值代表着该点的颜色(灰度图或者彩色图)。所谓直方图就是对图像的中的这些像素点的值进行统计,得到一个统一的整体的…

手眼标定学习笔记

目录 标定代码: 手眼标定原理学习 什么是手眼标定 手眼标定的目的 eye in hand eye to hand AXXB问题的求解 标定代码: GitHub - pumpkin-ws/HandEyeCalib 推荐博文: https://zhuanlan.zhihu.com/p/486592374 手眼标定原理学习 参…

YOLOv8: 标注石头、识别边缘及计算面积的方案

YOLOv8: 标注石头、识别边缘及计算面积的方案 引言 YOLO(You Only Look Once)是一种非常有效的实时目标检测算法,自其首次发布以来就受到了广泛的关注和应用。YOLOv8 是这一系列算法的最新版本,继承了之前版本的高效性和准确性&a…

如何在一台电脑上安装多个版本的JDK并且切换使用?

如何在一台电脑上安装多个版本的JDK并且切换使用? 文章目录 如何在一台电脑上安装多个版本的JDK并且切换使用?1.目录管理2.下载JDK3.配置环境变量4. 验证 1.目录管理 我们需要首先对不同版本的JDK进行版本管理,如下所示,我在C盘路…

vue3状态管理,pinia的使用

状态管理 我们知道组件与组件之间可以传递信息,那么我们就可以将一个信息作为组件的独立状态(例如,单个组件的颜色)或者共有状态(例如,多个组件是否显示)在组件之传递,这样的话我们希…

STM32作业实现(七)OLED显示数据

目录 STM32作业设计 STM32作业实现(一)串口通信 STM32作业实现(二)串口控制led STM32作业实现(三)串口控制有源蜂鸣器 STM32作业实现(四)光敏传感器 STM32作业实现(五)温湿度传感器dht11 STM32作业实现(六)闪存保存数据 STM32作业实现(七)OLED显示数据 STM32作业实现(八)触摸按…

最新h5st(4.7.2)参数分析与纯算法还原(含算法源码)

文章目录 1. 写在前面2. 加密分析3. 算法还原 【🏠作者主页】:吴秋霖 【💼作者介绍】:擅长爬虫与JS加密逆向分析!Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长期坚守并致力于Python…

HALCON-从入门到入门-最常用的算子-二值化

1.废话 图像处理中的二值化是一种将灰度图像转换为只有两种可能值(通常是0和255,分别代表黑色和白色)的过程。这个过程在数字图像处理中非常常见,因为它可以简化图像数据,突出图像的主要特征,并降低后续处…

5.25.12 数字组织病理学的自我监督对比学习

无监督学习可以弥补标记数据集的稀缺性。 无监督学习的一个有前途的子类是自监督学习,其目的是使用原始输入作为学习信号来学习显著特征。在这项工作中,我们解决了在没有任何监督的情况下学习领域特定特征的问题,以提高数字组织病理学界感兴…

【vue实战项目】通用管理系统:作业列表

目录 目录 1.前言 2.后端API 3.前端API 4.组件 5.分页 6.封装组件 1.前言 本文是博主前端Vue实战系列中的一篇文章,本系列将会带大家一起从0开始一步步完整的做完一个小项目,让你找到Vue实战的技巧和感觉。 专栏地址: https://blog…

【Linux】Linux工具——gcc/g++

1.使用vim更改信用名单——sudo 我们这里来补充sudo的相关知识——添加信任白名单用户 使用sudo就必须将使用sudo的那个账号添加到信用名单里,而且啊,只有超级管理员才可以添加 信用名单在/etc/sudoers里 我们发现它的权限只是可读啊,所以…

MD中 面料的物理属性参数

该图片是Marvelous Designer软件中"Fabric Physical Properties"(面料物理属性)面板的截图,用于调整面料在弯曲、折叠时的硬度(Buckling Stiffness)。 目标部分解释了调整Buckling Stiffness的作用:通过调整该百分比值来决定面料角落处的硬度。进入80%的Buckling St…

Linux网络编程:应用层协议|HTTPS

目录 1.预备知识 1.1.加密和解密 1.2.常见加密方式 1.2.1.对称加密 1.2.2.非对称加密 ​编辑 1.3.数据摘要(数据指纹)和数据签名 1.4.证书 1.4.1.CA认证 1.4.2.证书和数字签名 2.HTTPS协议 2.1.自行设计HTTPS加密方案 2.1.1.只使用对称加密 …

java调用科大讯飞离线语音合成SDK --内附完整项目

科大讯飞语音开放平台基础环境搭建 1.用户注册 注册科大讯飞开放平台账号 2.注册好后先创建一个自己的应用 创建完成后进入应用选择离线语音合成(普通版)可以看到我们开发需要的SDK,选择windows MSC点击下载。 3.选择你刚刚创建的应用,选择…

python安装pystan教程

简介 PyStan是Stan编程语言的Python接口,Stan是一种用于统计建模和数据分析的概率编程语言。PyStan使用户能够在Python环境中定义、编译和采样Stan模型。 安装步骤 首先,需要先安装 Cython pip install Cython -i https://mirrors.aliyun.com/pypi/sim…

Java学习20——Map接口

目录 一.Map: 1.基本介绍: 2.Map常用方法: 3.Map的遍历方法: 4.HashMap: 1.基本介绍: 2.HashMap底层扩容机制: 5.Hashtable: 1.基本介绍: 2.HashMap和Hashtable的对比&…