【LeetCode】K 个不同整数的子数组题解

HQ数字卡

关注

发布于: 2021 年 02 月 09 日

题目

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。

（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）

返回 A 中好子数组的数目。

代码

public class DayCode {    public static void main(String[] args) {        int[] A = new int[]{1,2,1,2,3};        int K = 2;        int ans = new DayCode().subArraysWithKDistinct(A, K);        System.out.println("ans is " + ans);    }
    /**     * https://leetcode-cn.com/problems/subarrays-with-k-different-integers/     * @param A     * @param K     * @return     */    public int subArraysWithKDistinct(int[] A, int K) {        return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);    }
    public int atMostKDistinct(int[] A, int K) {        int len = A.length;        int[] freq = new int[len + 1];        int left = 0;        int right = 0;        int count = 0;        int res = 0;        while (right < len) {            if (freq[A[right]] == 0) {                count++;            }            freq[A[right]]++;            right++;            while (count > K) {                freq[A[left]]--;                if (freq[A[left]] == 0) {                    count--;                }                left++;            }
            res += right - left;        }        return res;    }}

复制代码

总结

以上代码时间复杂度是 O(n),空间复杂度是 O(n)
这个题目在 LeetCode 上面是 hard 题目。需要认真分析，这个题目依然是滑动窗口的应用。难道是题目理解的转换，

恰好为 K 个子数组树木= 最多 K 个的子数组数目 - 最多 K-1 个子数组的数目

拆解成子问题之后，使用滑动窗口的思想来解决问题。

发布于: 2021 年 02 月 09 日阅读数: 11

原文链接:【http://xie.infoq.cn/article/5b75e2ea9f05edb887f1e2b66】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】K 个不同整数的子数组题解

题目

代码

总结

HQ数字卡

评论