992.K个不同整数的子数组

链接：992.K个不同整数的子数组
难度：Hard
标签：数组、哈希表、计数、滑动窗口
简介：返回 A 中好子数组的数目。

题解 1 - typescript

• 编辑时间：2021-02-10
• 执行用时：108ms
• 内存消耗：45.9MB
• 编程语言：typescript
• 解法介绍：转换题目为最多包含 K 种数组，进行相减得到解。

function subarraysWithKDistinct(A: number[], K: number): number {
  const atMostWithKDistinct = (k: number): number => {
    const len = A.length;
    const freq: number[] = new Array(len + 1).fill(0);
    let l = 0;
    let r = 0;
    let c = 0;
    let res = 0;
    while (r < len) {
      if (freq[A[r]]++ === 0) cpp;
      r++;
      while (c > k) {
        if (--freq[A[l]] === 0) c--;
        l++;
      }
      res += r - l;
    }
    return res;
  };
  return atMostWithKDistinct(K) - atMostWithKDistinct(K - 1);
}