【刷穿 LeetCode】992. K 个不同整数的子数组（困难）

宫水三叶的刷题日记

发布于 2021-02-20 09:54:54

6150

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

题目描述

给定一个正整数数组 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;
        }
    }
}

时间复杂度：对数组进行常数次扫描。复杂度为

O(n)

空间复杂度：

O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你可以看到「系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。」

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-09，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

腾讯云开发者社区

本文分享自宫水三叶的刷题日记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

腾讯云开发者社区

登录后参与评论

0 条评论

热度