点击 这里 可以查看更多算法面试相关内容~
题目描述
给定一个正整数数组 nums。
如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为好子数组。
例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
返回 nums 中好子数组的数目。
示例 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 <= 200001 <= nums[i] <= nums.length1 <= k <= nums.length
双指针滑动窗口解法
对原数组 nums 的每一个位置 i 而言：
- 找到其左边「最远」满足出现
k个不同字符的下标，记为p。这时候形成的区间为[p, i] - 找到其左边「最远」满足出现
k - 1个不同字符的下标，记为j。这时候形成的区间为[j, i] - 那么对于
j - p其实就是代表以 nums[i] 为右边界（必须包含 num[i]），不同字符数量「恰好」为 k 的子数组数量
网络异常，图片无法展示
|
我们使用 lower 数组存起每个位置的 k；使用 upper 数组存起每个位置的 j。
累积每个位置的 upper[i] - lower[i] 就是答案。
计算 lower 数组 和 upper 数组的过程可以使用双指针：
class Solution { public int subarraysWithKDistinct(int[] nums, int k) { int n = nums.length; int[] lower = new int[n], upper = new int[n]; find(lower, nums, k); find(upper, nums, k - 1); int ans = 0; for (int i = 0; i < n; i++) ans += upper[i] - lower[i]; return ans; } void find(int[] arr, int[] nums, int k) { int n = nums.length; int[] cnt = new int[n + 1]; int ans = 0; for (int i = 0, j = 0, sum = 0; i < n; i++) { int right = nums[i]; if (cnt[right] == 0) sum++; cnt[right]++; while (sum > k) { int left = nums[j++]; cnt[left]--; if (cnt[left] == 0) sum--; } arr[i] = j; } } } 复制代码
- 时间复杂度：对数组进行常数次扫描。复杂度为 O(n)O(n)O(n)
- 空间复杂度：O(n)O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。
为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
#算法与数据结构
#LeetCode题解
#算法面试
