给定一个正整数数组 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 <= 20000
1 <= nums[i] <= nums.length
1 <= 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;
}
}
}
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 */1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到「系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。」