有没有专门建设网站的公司,合肥房产网新楼盘价格,给网站做app,深圳最新出行政策文章目录1. 题目2. 解题1. 题目
给定一个正整数数组 A#xff0c;如果 A 的某个子数组中不同整数的个数恰好为 K#xff0c;则称 A 的这个连续、不一定独立的子数组为好子数组。
#xff08;例如#xff0c;[1,2,3,1,2] 中有 3 个不同的整数#xff1a;1#xff0c;2如果 A 的某个子数组中不同整数的个数恰好为 K则称 A 的这个连续、不一定独立的子数组为好子数组。
例如[1,2,3,1,2] 中有 3 个不同的整数12以及 3。
返回 A 中好子数组的数目。
示例 1
输入A [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
输入A [1,2,1,3,4], K 3
输出3
解释恰好由 3 个不同整数组成的子数组
[1,2,1,3], [2,1,3], [1,3,4].提示
1 A.length 20000
1 A[i] A.length
1 K A.length来源力扣LeetCode 链接https://leetcode-cn.com/problems/subarrays-with-k-different-integers 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考官方思路每次遍历一个右端点 r以该右端点为结束的满足题意的子数组有多少个左端点有两个极限位置 l1, l2[l1, r]刚好有 k 个不同数字[l2, r] 刚好有 k-1 个不同数字累加 满足条件的l2 - l1
class Solution {
public:int subarraysWithKDistinct(vectorint A, int K) {int l1 0, l2 0, r 0, n A.size();int ct1 0, ct2 0, ans 0;vectorint nums1(n1, 0), nums2(n1, 0);while(r n){if(nums1[A[r]] 1)ct1;if(nums2[A[r]] 1)ct2;while(ct1 K){if(--nums1[A[l1]] 0)ct1--;l1;}while(ct2 K){if(--nums2[A[l2]] 0)ct2--;l2;}ans l2-l1;r;}return ans;}
};40 ms 32.5 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
