LeetCoe992 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].
提示：
1 <= nums.length <= 2 * 104
1 <= nums[i], k <= nums.length
滑动窗口
复杂度: O(n)。
枚举子数组的左边界left，时间复杂度O(n)；枚举r1,r2时间复杂度O(n)。由于r1和r2没有复位，所以总时间复杂度是O(n)。
| r1 | nums[left,r1)有k个不同的整数，如果有多个符合的r1，取最小值。如果没有符合的r1，则r1为m_c |
| r2 | nums[left,r2)有k+1个不同的整数，如果有多个符合的r2，取最小值。如果没有符合的r2，则r2为m_c |
如果没有符合的r1，则忽略或直接退出。
| 如果r2合法 | 则nums[left,r)刚好有k个数,r取值范围[r1,r2),数量为r2-r1 |
| 如果r2非法则 | nums[left,r)刚好有k个数,r取值范围[r1,m_c],数量r2+1-r1 |
代码
核心代码
template<class KEY> class CKeyCount { public: void Add(const KEY& key, int iCount) { Cnt[key] += iCount; if (0 == Cnt[key]) { Cnt.erase(key); } } std::unordered_map<KEY, int> Cnt; }; class Solution { public: int subarraysWithKDistinct(vector<int>& nums, int k) { m_c = nums.size(); CKeyCount<int> cnt1,cnt2; int r1 = 0, r2 = 0; int iRet = 0; for (int left = 0; left < nums.size(); left++) { while ((r1 < m_c)&&( cnt1.Cnt.size() < k ) ) { cnt1.Add(nums[r1++],1); } while ((r2 < m_c) && (cnt2.Cnt.size() < k+1)) { cnt2.Add(nums[r2++], 1); } if (cnt1.Cnt.size() < k ) { break; } iRet += r2 - r1 + (cnt2.Cnt.size()==k); cnt1.Add(nums[left], -1); cnt2.Add(nums[left], -1); } return iRet; } int m_c; };
2023年5月版
class Solution { public: int subarraysWithKDistinct(vector& nums, int k) { m_c = nums.size(); if (1 == k) { return DoK1(nums); } std::unordered_map mValueNum; std::unordered_map mIndexs; int left = 0, right = 0; //[i,vR1[i])表示以索引i开头符合条件的最短子串，[i,vR2[i]]表示以索引i开头符合条件的最长子串 //-1表示没有符合条件的子串 vector vR1(m_c,-1), vR2(m_c,-2); while ((right < m_c) && (mValueNum.size() < k )) { mValueNum[nums[right]]++; mIndexs[nums[right]].emplace(right); right++; } if (mValueNum.size() != k) { return 0; } vR1[0] = right; for (int left = 0; left < m_c; left++) { //[left,right) 全部符合条件 while ((right < m_c) && (mValueNum.count(nums[right]))) { const int iRightValue = nums[right]; mValueNum[iRightValue]++; mIndexs[iRightValue].emplace(right); right++; } vR2[left] = right; //删除索引为left的元素 const int iValueLeft = nums[left]; mIndexs[iValueLeft].pop(); if (1 == mValueNum[iValueLeft]) { mValueNum.erase(iValueLeft); while ((right < m_c) && (mValueNum.size() < k)) { const int iRightValue = nums[right]; mValueNum[iRightValue]++; mIndexs[iRightValue].emplace(right); right++; } if (mValueNum.size() == k) { vR1[left + 1] = right; } else { break; } } else { vR1[left + 1] = max(vR1[left], mIndexs[iValueLeft].front()+1); mValueNum[iValueLeft]–; } } int iRet = 0; for (int i = 0; i < m_c; i++) { iRet += vR2[i] - vR1[i]+1; } return iRet; } int DoK1(const vector& nums) { int iRet = 0; int iNum = 1; int iPre = nums[0]; for (int i = 1; i < m_c; i++) { if (nums[i] == iPre) { iNum++; } else { iRet += iNum*(iNum + 1) / 2; iNum = 1; iPre = nums[i]; } } iRet += iNum*(iNum + 1) / 2; return iRet; } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。
