Leetcode992-K个不同整数的子数组[两种方法] 关键词 滑窗

2024-03-19 01:04

本文主要是介绍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.

具体到代码实现,对于每一个右边界(即将加入滑窗)的值来说:

  1. 如果这个值曾经在滑窗中出现过,则把该值加入滑窗之后,滑窗内仍然是恰好K种数,那么pl“尝试右移”:cnt数组相应减少,直到遇到第一个将cnt的某个非零值减到0位置的位置tmp_pl,那么tmp-pl就是此时右边界对应所有左边界的个数。然后把pl~tmp_pl区间内的数再加回cnt数组(恢复)。
  2. 如果这个值没有在滑窗中出现,那么把该值加入滑窗之后,滑窗内就有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个不同整数的子数组[两种方法] 关键词 滑窗的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/824301

相关文章

golang中reflect包的常用方法

《golang中reflect包的常用方法》Go反射reflect包提供类型和值方法,用于获取类型信息、访问字段、调用方法等,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值... 目录reflect包方法总结类型 (Type) 方法值 (Value) 方法reflect包方法总结

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Python中注释使用方法举例详解

《Python中注释使用方法举例详解》在Python编程语言中注释是必不可少的一部分,它有助于提高代码的可读性和维护性,:本文主要介绍Python中注释使用方法的相关资料,需要的朋友可以参考下... 目录一、前言二、什么是注释?示例:三、单行注释语法:以 China编程# 开头,后面的内容为注释内容示例:示例:四

一文详解Git中分支本地和远程删除的方法

《一文详解Git中分支本地和远程删除的方法》在使用Git进行版本控制的过程中,我们会创建多个分支来进行不同功能的开发,这就容易涉及到如何正确地删除本地分支和远程分支,下面我们就来看看相关的实现方法吧... 目录技术背景实现步骤删除本地分支删除远程www.chinasem.cn分支同步删除信息到其他机器示例步骤

在Golang中实现定时任务的几种高效方法

《在Golang中实现定时任务的几种高效方法》本文将详细介绍在Golang中实现定时任务的几种高效方法,包括time包中的Ticker和Timer、第三方库cron的使用,以及基于channel和go... 目录背景介绍目的和范围预期读者文档结构概述术语表核心概念与联系故事引入核心概念解释核心概念之间的关系

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复