【滑动窗口】C++算法:K 个不同整数的子数组

作者推荐

动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本

本题涉及知识点

滑动窗口

LeetCoe992 K 个不同整数的子数组

给定一个正整数数组 nums和一个整数 k,返回 nums 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k,则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 3。
子数组 是数组的 连续 部分。
示例 1:
输入:nums = [1,2,1,2,3], k = 2
输出:7
解释:恰好由 2 个不同整数组成的子数组:[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2:
输入:nums = [1,2,1,3,4], k = 3
输出:3
解释:恰好由 3 个不同整数组成的子数组:[1,2,1,3], [2,1,3], [1,3,4].
提示:
1 <= nums.length <= 2 * 104
1 <= nums[i], k <= nums.length

滑动窗口

复杂度: O(n)。
枚举子数组的左边界left,时间复杂度O(n);枚举r1,r2时间复杂度O(n)。由于r1和r2没有复位,所以总时间复杂度是O(n)。

r1nums[left,r1)有k个不同的整数,如果有多个符合的r1,取最小值。如果没有符合的r1,则r1为m_c
r2nums[left,r2)有k+1个不同的整数,如果有多个符合的r2,取最小值。如果没有符合的r2,则r2为m_c

如果没有符合的r1,则忽略或直接退出。

如果r2合法则nums[left,r)刚好有k个数,r取值范围[r1,r2),数量为r2-r1
如果r2非法则nums[left,r)刚好有k个数,r取值范围[r1,m_c],数量r2+1-r1

代码

核心代码

template<class KEY>
class CKeyCount
{
public:void Add(const KEY& key, int iCount){Cnt[key] += iCount;if (0 == Cnt[key]){Cnt.erase(key);}}std::unordered_map<KEY, int> Cnt;
};class Solution {
public:int subarraysWithKDistinct(vector<int>& nums, int k) {m_c = nums.size();CKeyCount<int> cnt1,cnt2;int r1 = 0, r2 = 0;int iRet = 0;for (int left = 0; left < nums.size(); left++){while ((r1 < m_c)&&( cnt1.Cnt.size() < k ) ){cnt1.Add(nums[r1++],1);}while ((r2 < m_c) && (cnt2.Cnt.size() < k+1)){cnt2.Add(nums[r2++], 1);}if (cnt1.Cnt.size() < k ){break;			}iRet += r2 - r1 + (cnt2.Cnt.size()==k);	cnt1.Add(nums[left], -1);cnt2.Add(nums[left], -1);}return iRet;}int m_c;
};

2023年5月版

class Solution {
public:
int subarraysWithKDistinct(vector& nums, int k) {
m_c = nums.size();
if (1 == k)
{
return DoK1(nums);
}
std::unordered_map<int, int> mValueNum;
std::unordered_map<int, std::queue> mIndexs;
int left = 0, right = 0;
//[i,vR1[i])表示以索引i开头符合条件的最短子串,[i,vR2[i]]表示以索引i开头符合条件的最长子串
//-1表示没有符合条件的子串
vector vR1(m_c,-1), vR2(m_c,-2);
while ((right < m_c) && (mValueNum.size() < k ))
{
mValueNum[nums[right]]++;
mIndexs[nums[right]].emplace(right);
right++;
}
if (mValueNum.size() != k)
{
return 0;
}
vR1[0] = right;
for (int left = 0; left < m_c; left++)
{
//[left,right) 全部符合条件
while ((right < m_c) && (mValueNum.count(nums[right])))
{
const int iRightValue = nums[right];
mValueNum[iRightValue]++;
mIndexs[iRightValue].emplace(right);
right++;
}
vR2[left] = right;
//删除索引为left的元素
const int iValueLeft = nums[left];
mIndexs[iValueLeft].pop();
if (1 == mValueNum[iValueLeft])
{
mValueNum.erase(iValueLeft);
while ((right < m_c) && (mValueNum.size() < k))
{
const int iRightValue = nums[right];
mValueNum[iRightValue]++;
mIndexs[iRightValue].emplace(right);
right++;
}
if (mValueNum.size() == k)
{
vR1[left + 1] = right;
}
else
{
break;
}
}
else
{
vR1[left + 1] = max(vR1[left], mIndexs[iValueLeft].front()+1);
mValueNum[iValueLeft]–;
}
}
int iRet = 0;
for (int i = 0; i < m_c; i++)
{
iRet += vR2[i] - vR1[i]+1;
}
return iRet;
}
int DoK1(const vector& nums)
{
int iRet = 0;
int iNum = 1;
int iPre = nums[0];
for (int i = 1; i < m_c; i++)
{
if (nums[i] == iPre)
{
iNum++;
}
else
{
iRet += iNum*(iNum + 1) / 2;
iNum = 1;
iPre = nums[i];
}
}
iRet += iNum*(iNum + 1) / 2;
return iRet;
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法C++ 实现。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

右键添加 idea 打开功能

1.开始运行regedit 2.找到: HKEY_LOCAL_MACHINE\SOFTWARE\Classes\Directory\shell _3.开始设置 一、右键shell目录新建项Idea二、右键Idea新建command三、选择Idea 右侧空白出新建字符串 名字为Icon 值填入idea的运行程序地址 四、选择command 默认项填入idea的运行程序地址…

Vue3-29-路由-编程式导航的基本使用

补充一个知识点 路由配置中的 name 属性 &#xff1a; 可以给你的 路由 指定 name属性&#xff0c;称之为 命名路由。 这个 name 属性 在 编程式导航 传参时有重要的作用。 命名路由的写法如下 &#xff1a; 像指定 path 一样&#xff0c;直接指定一个 name 属性即可。{path:/d…

python+django网上购物商城系统o9m4k

语言&#xff1a;Python 框架&#xff1a;django/flask可以定制 软件版本&#xff1a;python3.7.7 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发工具pycharm/vscode都可以 前端框架:vue.js 系统使用过程主要涉及到管理员和用户两种角色&#xff0c;主要包含个…

智能优化算法应用:基于减法平均算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于减法平均算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于减法平均算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.减法平均算法4.实验参数设定5.算法结果6.…

人工智能_机器学习078_聚类算法_概念介绍_聚类升维_降维_各类聚类算法_有监督机器学习_无监督机器学习---人工智能工作笔记0118

首先看一下什么是聚类,我们可以进入sklearn的官网去看看 可以看到这里,首先classification 这个分类我们学完了,然后就是regression回归我们也学完了对吧,其实我们现实生活中的,大部分问题就是 这两种问题就可以解决了. 然后我们再来看一个: clustering,这个就是聚类对吧.聚类算…

提升数据库性能的关键指南-Oracle AWR报告

文章目录 一、了解AWR报告&#xff1a;数据库性能的仪表盘二、生成AWR报告三、解读AWR报告的关键部分1.报告开头的系统基础信息2.ADDM发现3.负载概览(Load Profile)4.参数文件5.顶级前台等待事件6.SQL 统计信息-顶级SQL7.SGA Advisory AND PAG Advisory 一、了解AWR报告&#x…

Linux之磁盘分区,挂载

Linux分区 分区介绍 对linux来说无论有几个分区&#xff0c;分给哪个目录使用&#xff0c;归根结底只有一个根目录&#xff0c;linux中每个分区都是用来组成整个文件系统的一部分。linux采用“载入"的处理方法&#xff0c;他的整个文件系统中包含一整套的文件和目录&…

香橙派 ubuntu实现打通内网,外网双网络,有线和无线双网卡

当香橙派 ubuntu 连了有线&#xff0c;和无线时&#xff0c;默认请求外网时&#xff0c;只走一个网卡&#xff0c;如走了内网网卡&#xff0c;就只能访问内访问&#xff0c;访问不了外网&#xff1b;走了外网网卡就只能访问外网&#xff0c;访问不了内网&#xff1b; 实现双网…

【开源】基于Vue+SpringBoot的公司货物订单管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 客户管理模块2.2 商品维护模块2.3 供应商管理模块2.4 订单管理模块 三、系统展示四、核心代码4.1 查询供应商信息4.2 新增商品信息4.3 查询客户信息4.4 新增订单信息4.5 添加跟进子订单 五、免责说明 一、摘要 1.1 项目…

手写Spring与基本原理--简易版

文章目录 手写Spring与基本原理解析简介写一个简单的Bean加载容器定义一个抽象所有类的BeanDefinition定义一个工厂存储所有的类测试 实现Bean的注册定义和获取基于Cglib实现含构造函数的类实例化策略Bean对象注入属性和依赖Bean的功能Spring.xml解析和注册Bean对象实现应用上下…

2023-12-29 服务器开发-centos部署ftp

摘要: 2023-12-29 服务器开发-centos-部署ftp 部署ftp vsftpd&#xff08;very secure FTP daemon&#xff09;是Linux下的一款小巧轻快、安全易用的FTP服务器软件。本教程介绍如何在Linux实例上安装并配置vsftpd。 前提条件 已创建ECS实例并为实例分配了公网IP地址。 背景…

Vue3-26-路由-useRouter 和 useRoute 两个API 的作用介绍

先来说说两个API 的作用 useRouter() : 返回的是项目中的 路由实例的对象 可以通过这个实例对象进行路由的逻辑跳转 useRoute() : 返回的是当前的 路由对象&#xff0c; 可以在当前路由对象中获取到路由名称、路由参数、路由路径等玩完整的路由信息。 写个案例看一下具体是什么…

词法语法语义分析程序设计及实现,包含出错提示和错误恢复

词法说明 (1)关键字 main, int, char, if, else, for, while, void (2)运算符 - * / < < > > ! (3)界符 ; ( ) { } (4)标识符 ID letter(letter|digit)* (5)整型常数 NUM digit digit* (6)空格 ‘ ‘ ‘\n’ ‘\r’ ‘\t’ 空格用来分隔ID,NUM,运算符,界…

从AMI镜像恢复AWS Amazon Linux 2实例碰到的VNC服务以及Chrome浏览器无法启动的问题

文章目录 小结问题及解决VNC服务无法启动Chrome浏览器无法启动 参考 小结 将Amazon Linux 2保存为AMI (Amazon Machine Images)后&#xff0c;恢复成EC2 Instance (实例)后&#xff0c;VNC服务以及Chrome浏览器无法启动&#xff0c;进行了解决。 问题及解决 如果要将一个EC2…

从物联网到 3D 打印:硬件相关的开源项目概览 | 开源专题 No.52

arendst/Tasmota Stars: 20.4k License: GPL-3.0 Tasmota 是一款为 ESP8266 和 ESP32 设备提供的替代固件&#xff0c;具有易于配置的 webUI、OTA 更新、定时器或规则驱动的自动化功能以及通过 MQTT、HTTP、串口或 KNX 进行完全本地控制。该项目主要特点包括&#xff1a; 支持…

2024年上海中考数学提分的有效方法:吃透近十年中考数学真题

再过两天2023年就翻篇了&#xff0c;进入2024年&#xff0c;初三的学子们可能立刻就感觉到中考就在眼前。根据教育部门官方发消息&#xff0c;2024年中考日期安排在2024年6月19-21日&#xff0c;也意味着距离中考还有6个月多一点。 那么如何充分利用这最后的六个多月&#xff…

部署谷歌的Gemini大模型

前言 本文将介绍如何使用Docker、Docker-Compose私有化部署谷歌的Gemini大模型&#xff0c;以及没有服务器的情况下如何使用Vercel来部署。 Demo: 使用新加坡云服务器部署&#xff1a;Gemini Pro Chat (snowice.eu.org) 使用Vercel部署&#xff1a;Gemini Pro Chat (snowice.eu…

基于JAVA的考研专业课程管理系统 开源项目

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 考研高校模块2.3 高校教师管理模块2.4 考研专业模块2.5 考研政策模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 考研高校表3.2.2 高校教师表3.2.3 考研专业表3.2.4 考研政策表 四、系统展示五、核…

实现 Spring Boot 项目热重载,无需重启,省时省力

实现 Spring Boot 项目热重载&#xff0c;无需重启&#xff0c;省时省力 插件介绍 通过 JRebel 插件 实现 Spring Boot 项目热重载。类似于前端 Webpack 热重载功能 无需重启&#xff0c;省时省力 安装插件 打开 IDEA 在插件中搜索&#xff1a;JRebel 安装成功后重启IDEA …