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