当前位置: 首页 > news >正文

992. K 个不同整数的子数组

992. 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].


C代码:滑窗

int subarraysWithKDistinct(int* nums, int numsSize, int k){int hash[20001] = {0};int l = 0;int cnt = 0;int ans = 0;int del = 0;for (int r = 0; r < numsSize; ++r) {hash[nums[r]]++;if (hash[nums[r]] == 1) {cnt++;}while (cnt > k) { // 若只是cnt > k就收缩左侧,那么只满足窗口中的类,12 121 1212满足了,21却没有满足hash[nums[l]]--;if (hash[nums[l]] == 0) {cnt--;del = 0;  // 元素种类超,归零}++l;}                            // 在cnt<=k 的情况下,窗口左侧若元素个数为1,即再往右移就会删除元素while (cnt == k && hash[nums[l]] > 1) {  // 窗口左侧的第一个元素次数>1(种类满足、元素次数有余)1222 1112222  1112221222  12221->21hash[nums[l++]]--;++del;// ans+=1;  //error}if (cnt == k) {ans += del + 1;// ans += 1;  //error}}return ans;
}// 121213:
// 12  ans=1 del=0
// 121->21 ans=3 del=1(121) 21
// 212->12 ans=6 del=2(1212 212) 12
// 121->21 ans=10 del=3(12121 2121 121) 21 // 以每个当前子串为向前回溯,涵盖所有可能
// 213->13 ans=11 del=0
http://www.lryc.cn/news/172035.html

相关文章:

  • Vue 使用vue-cli构建SPA项目(超详细)
  • SpringBoot工程模板
  • 学习SLAM:SLAM进阶(十)暴力更改ROS中的PCL库
  • js 事件流、事件冒泡、事件捕获、阻止事件的传播
  • 一家美国公司被黑,一个拉美国家政务服务瘫痪
  • c++ QT 十八位时间戳转换
  • 全国职业技能大赛云计算--高职组赛题卷④(容器云)
  • 【TCP】延时应答 与 捎带应答
  • URL与URI小结
  • QT--day5
  • 在windows和linux上玩转Tensorrt
  • 七天学会C语言-第五天(函数)
  • 340. 至多包含 K 个不同字符的最长子串
  • 【分布式计算】副本数据Replicated Data
  • erlang练习题(二)
  • CRM软件系统价格不同的原因
  • json数据解析
  • Verilog零基础入门(边看边练与测试仿真)-状态机-笔记(7-10讲)
  • 【Hadoop】HDFS API 操作大全
  • Webpack打包图片
  • DipC 构建基因组 3D 结构(学习笔记)
  • Qt中音频的使用
  • [centos]centos7源码编译cmake报错Could NOT find OpenSSL
  • vue若依前端项目搭建
  • 基于win32实现TB登陆滑动验证
  • vue学习-07todoList案例与浏览器本地存储
  • 探索智能应用的基石:多模态大模型赋能文档图像处理
  • 自动化发布npm包小记
  • 详解机器视觉性能指标相关概念——混淆矩阵、IoU、ROC曲线、mAP等
  • 想要精通算法和SQL的成长之路 - 预测赢家