Leetcode992-K个不同整数的子数组[两种方法] 关键词 滑窗
文章目录
- 题目
- 方法一:滑窗右端每次+1,左端来回滑动
- 方法二:(最多K种的子串数) - (最多K-1种的子串数) = 恰好K种
题目

1 <= nums.length <= 20000
1 <= nums[i], k <= nums.length
方法一:滑窗右端每次+1,左端来回滑动
这道题初步看上去像滑窗。滑窗解决的问题是“最长”,比如找“无重复字符的最长子串”、“特定排列的子串”。通用方法就是滑窗右侧尽可能向右,直到滑窗内元素的个数不满足要求那么滑窗左侧右移。
本题考虑的不是“最多K个不同整数”,而是“恰好K个不同整数”。
我的办法(方法一)是先用滑窗找到“最多K个不同整数”的每个左右边界,然后对于这其中的每一个右边界,左边界“尝试右移”,找到全部合适的左边界。比如序列12123,对于第二个2来说,“最多2个不同整数”,就是1212,满足条件的左边界有3个,[1]212、[2]12、[1]2.
具体到代码实现,对于每一个右边界(即将加入滑窗)的值来说:
- 如果这个值曾经在滑窗中出现过,则把该值加入滑窗之后,滑窗内仍然是恰好K种数,那么pl“尝试右移”:cnt数组相应减少,直到遇到第一个将cnt的某个非零值减到0位置的位置tmp_pl,那么tmp-pl就是此时右边界对应所有左边界的个数。然后把pl~tmp_pl区间内的数再加回cnt数组(恢复)。
- 如果这个值没有在滑窗中出现,那么把该值加入滑窗之后,滑窗内就有K+1种数了,此时pl必须右移。右移到合适位置后,再进行1中的“尝试右移”操作。
class Solution {int cnt[20010] = {0};int ans = 0;public:int subarraysWithKDistinct(vector<int>& nums, int k) {int pl = 0, pr = 0, k2 = 0;// 先找k个不同的,定下初始滑窗位置 左闭右开for (; pr < nums.size() && k2 < k; pr++)if (++cnt[nums[pr]] == 1) k2++;if (k2 < k) return 0;ans++;// 开始滑动while (pr < nums.size()) {// 先尝试pl右移int tmp_pl = pl;while (cnt[nums[tmp_pl]] > 1) {ans++;cnt[nums[tmp_pl]]--; tmp_pl++;}// 恢复while (tmp_pl > pl) {tmp_pl--;cnt[nums[tmp_pl]]++;}// if 下一个数是旧数,加入if (cnt[nums[pr]] > 0) {cnt[nums[pr]]++; pr++;ans++;}// if 下一个数是新数,pl右移至窗内种类数-1else {cnt[nums[pr]]++; pr++;do {cnt[nums[pl]]--;pl++;} while (cnt[nums[pl - 1]] > 0);ans++;}}// 尝试pl右移int tmp_pl = pl;while (cnt[nums[tmp_pl]] > 1) {ans++;cnt[nums[tmp_pl]]--;tmp_pl++;}return ans;}
};
时间复杂度:最坏是Onn,但是实际还不错。

方法二:(最多K种的子串数) - (最多K-1种的子串数) = 恰好K种
这个方法是官方题解法。
还是12123,且K=2这个例子,对于1212来说,有3个左边界可以满足“恰好K种”,这个3是怎么算出来的呢?最多K-1种的左边界是1个,一共4个潜在的左边界,4-1=3.
(最多K种的子串数) - (最多K-1种的子串数) = 恰好K种
时间复杂度On
相关文章:
Leetcode992-K个不同整数的子数组[两种方法] 关键词 滑窗
文章目录 题目方法一:滑窗右端每次1,左端来回滑动方法二:(最多K种的子串数) - (最多K-1种的子串数) 恰好K种 题目 1 < nums.length < 20000 1 < nums[i], k < nums.length 方法一…...
【闲聊】-后端框架发展史
框架,是为了解决系统复杂性,提升开发效率而产生的工具,主要服务于研发人员。 当然,框架还有更深层的作用,框架的沉淀是一种高级的抽象,会将人类的业务逐步抽象为统一标准又灵活可变的结构,为各行…...
界面控件DevExpress ASP.NET Scheduler - 助力快速交付个人信息管理系统(下)
DevExpress ASP. NET Scheduler组件能完全复制Microsoft Outlook Scheduler的样式和功能,具有日、周、月和时间轴视图,并包括内置的打印支持,因此用户可以在尽可能短的时间内交付全功能的个人信息管理系统。在上文中(点击这里回顾…...
机器学习-04-分类算法-01决策树
总结 本系列是机器学习课程的系列课程,主要介绍机器学习中分类算法,本篇为分类算法开篇与决策树部分。 参考 决策树——ID3和C4.5(理论图解公式推导) 策略产品经理必读系列—第七讲ID3、C4.5和CART算法详解 决策树(…...
探索大数据时代的决策利器:如何有效应对海量数据?
随着信息技术的快速发展,大数据时代已经到来,海量数据成为了我们生活和工作中不可忽视的一部分。这些数据来自各个方面:社交媒体、传感器、网络交易、移动设备等,每天都在以惊人的速度增长。但是,面对如此庞大的数据量,我们该如何有效地应对呢?本文将探索大数据时代的决…...
Linux 学习笔记(16)
十六、 计划任务 在很多时候为了自动化管理系统,我们都会用到计划任务,比如关机,管理,备份之类的操作,我 们都可以使用计划任务来完成,这样可以是管理员的工作量大大降低,而且可靠度更好。 l…...
【C语言】打印闰年
输⼊⼀个年份year,判断year是否是闰年 闰年判断的规则: 1, 能被4整除并且不能被100整除是闰年 2,能被400整除是闰年 结合起来如下: if ((year % 4 0 && year % 100 ! 0) || (year % 400 0)) 代码如下&…...
外贸入门,很残忍但很真实的外贸真相
如果你是小白入行外贸,第一家选择的公司大概率会决定你以后的客户开发模式。 外贸老鸟们可以留言讨论下自己是不是被说中了。 如果新人选择的第一家公司是靠B2B网站,展会或者官网询盘分发,公司每年会花大量的广告费用获客,你会很快…...
【Linux网络编程七】网络序列化和反序列化(网络版本计算器)
【Linux网络编程七】网络序列化和反序列化(网络版本计算器) 一.网络读取问题【解决方案】1.定制协议2.序列化和反序列化3.添加报头①封包②解包 4.框架总结 二.自定义协议:网络计算器协议Ⅰ.客户端发送请求,服务器端接收请求1.构建请求(结构化…...
算法打卡day17|二叉树篇06|Leetcode 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树
算法题 Leetcode 654.最大二叉树 题目链接:654.最大二叉树 大佬视频讲解:最大二叉树视频讲解 个人思路 大概思路就是在数组中 找最大值的节点作为当前节点,用最大值的index切割左右子树的区间,往复循环到数组元素为0; 解法 递…...
C语言之数据在计算机内部的存储
文章目录 一、前言二、类型的基本归类1、整型家族2、浮点数家族3、构造类型4、指针类型 三、整型在内存中的存储1、原码、反码、补码1.1 概念1.2 原码与补码的转换形式1.3 计算机内部的存储编码 2、大小端介绍~~2.1 为什么要有大端和小端之分?2.2 大(小&…...
程序人生——Java中基本类型使用建议
目录 引出Java中基本类型使用建议建议21:用偶判断,不用奇判断建议22:用整数类型处理货币建议23:不要让类型默默转换建议24:边界、边界、还是边界建议25:不要让四舍五入亏了一方 建议26:提防包装…...
Pikachu 靶场搭建
文章目录 环境说明1 Pikachu 简介2 Pikachu 安装 环境说明 操作系统:Windows 10PHPStudy 版本: 8.1.1.3Apache 版本:2.4.39MySQL 版本 5.7.26 1 Pikachu 简介 Pikachu是一个使用“PHP MySQL” 开发、包含常见的Web安全漏洞、适合Web渗透测试学习人员练…...
机器学习-绪论
机器学习致力于研究如何通过计算的手段、利用经验来改善系统自身的性能。在计算机系统中,“经验”通常以“数据”的形式存在,因此,机器学习所研究的主要内容,是关于在计算机上从数据中产生“模型”的算法,即“学习算法…...
mysql 索引(为什么选择B+ Tree?)
索引实现原理 索引:排好序的数据结构 优点:降低I/O成本,CPU的资源消耗(数据持久化在磁盘中,每次查询都得与磁盘交互) 缺点:更新表效率变慢,(更新表数据,还要…...
蓝桥杯-带分数
法一 /* 再每一个a里去找c,他们共用一个st数组,可以解决重复出现数字 通过ac确定b,b不能出现<0 b出现的数不能和ac重复*/import java.util.Scanner;public class Main {static int n,res;static boolean[] st new boolean[15];static boolean[] backup new boolean[15];…...
消息队列面试题
目录 1. 为什么使用消息队列 2. 消息队列的缺点 3. 消息队列如何选型? 4. 如何保证消息队列是高可用的 5. 如何保证消息不被重复消费(见第二条) 6. 如何保证消息的可靠性传输? 7. 如何保证消息的顺序性(即消息幂…...
Android和IOS应用开发-Flutter 应用中实现记录和使用全局状态的几种方法
文章目录 在Flutter中记录和使用全局状态使用 Provider步骤1步骤2步骤3 使用 BLoC步骤1步骤2步骤3 使用 GetX:步骤1步骤2步骤3 在Flutter中记录和使用全局状态 在 Flutter 应用中,您可以使用以下几种方法来实现记录和使用全局状态,并在整个应…...
若依 ruoyi-cloud [网关异常处理]请求路径:/system/user/getInfo,异常信息:404
这里遇到的情况是因为nacos中的配置文件与项目启动时的编码不一样,若配置文件中有中文注释,那么用idea启动项目的时候,在参数中加上 -Dfile.encodingutf-8 ,保持编码一致,(用中文注释的配置文件,…...
自然语言处理里预训练模型——BERT
BERT,全称Bidirectional Encoder Representation from Transformers,是google在2018年提出的一个预训练语言模型,它的推出,一举刷新了当年多项NLP任务值的新高。前期我在零、自然语言处理开篇-CSDN博客 的符号向量化一文中简单介绍…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...
手动给中文分词和 直接用神经网络RNN做有什么区别
手动分词和基于神经网络(如 RNN)的自动分词在原理、实现方式和效果上有显著差异,以下是核心对比: 1. 实现原理对比 对比维度手动分词(规则 / 词典驱动)神经网络 RNN 分词(数据驱动)…...
