市北区大型网站建设wordpress 适配 手机

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