成都网站建设公司汇总,西安百度竞价,成都宅天下装饰公司怎么样,网站定制合同题目链接#xff1a;https://leetcode.cn/problems/subarrays-with-k-different-integers/description/
题目大意#xff1a;给一个数组nums[]#xff0c;求【不同元素刚好为k个】的子列的个数。子列要求连续。
思路#xff1a;主要是转换题意#xff0c;可以先求【不同…题目链接https://leetcode.cn/problems/subarrays-with-k-different-integers/description/
题目大意给一个数组nums[]求【不同元素刚好为k个】的子列的个数。子列要求连续。
思路主要是转换题意可以先求【不同元素最多为k个】的子列数然后再求【不同元素最多为k-1个】的子列数两者相减就是【不同元素刚好为k个】的子列数。思路有点像前缀和。
那么可以用滑动窗口来解决。对于每一个固定的右端点r找一个左端点l从最左边开始找使得刚好[l, r]区间里的不同元素个数刚好为k这样就是最多为k个的情况。然后这个l可以作为下一轮的新起点因为下一轮r往右移动了使得不同元素数只会增加或者不变l没必要再从0开始只要从上一轮的l开始就行了。
每一轮中的r-l刚好就是【新增子列数】因为新增子列是连续的并且必然包含nums[r]这些子列即为以r为右端点长度为1, 2, ..., r-l的子列。
完整代码
class Solution {
public:int kDis(vectorint nums, int k) {int n nums.size();vectorint freq(n1, 0);int l 0, r 0, res 0;int disn 0;while (r n) {if (freq[nums[r]] 0)disn;freq[nums[r]];r;while (disn k) {freq[nums[l]]--;if (freq[nums[l]] 0)disn--;l;}res r - l;}return res;}int subarraysWithKDistinct(vectorint nums, int k) {return kDis(nums, k) - kDis(nums, k-1);}
};
