北京网站开发浩森宇特,h5免费制作平台无水印,制作网站代码吗,海南省住房公积金管理局官网文章目录 题目方法一#xff1a;滑窗右端每次1#xff0c;左端来回滑动方法二#xff1a;#xff08;最多K种的子串数#xff09; - #xff08;最多K-1种的子串数#xff09; 恰好K种 题目 1 nums.length 20000 1 nums[i], k nums.length
方法一… 文章目录 题目方法一滑窗右端每次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数组恢复。如果这个值没有在滑窗中出现那么把该值加入滑窗之后滑窗内就有K1种数了此时pl必须右移。右移到合适位置后再进行1中的“尝试右移”操作。
class Solution {int cnt[20010] {0};int ans 0;public:int subarraysWithKDistinct(vectorint 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且K2这个例子对于1212来说有3个左边界可以满足“恰好K种”这个3是怎么算出来的呢最多K-1种的左边界是1个一共4个潜在的左边界4-13.
最多K种的子串数 - 最多K-1种的子串数 恰好K种
时间复杂度On
