# 資訊

:::info
- Question: 992. Subarrays with K Different Integers
- From: Leetcode Daily Challenge 2024.03.30
- Difficulty: Hard
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

Given an integer array `nums` and an integer `k`, return the number of good subarrays of `nums`.

A **good array** is an array where the number of different integers in that array is exactly `k`.

For example, `[1,2,3,1,2]` has 3 different integers: `1`, `2`, and `3`.
A **subarray** is a contiguous part of an array.

> Example 1:
:::success
* Input: `nums = [1,2,1,2,3]`, `k = 2`
* Output: 7
* Explanation: Subarrays formed with exactly 2 different integers: `[1,2]`, `[2,1]`, `[1,2]`, `[2,3]`, `[1,2,1]`, `[2,1,2]`, `[1,2,1,2]`
:::

> Example 2:
:::success
* Input: `nums = [1,2,1,3,4]`, `k = 3`
* Output: 3
* Explanation: Subarrays formed with exactly 3 different integers: `[1,2,1,3]`, `[2,1,3]`, `[1,3,4]`.
:::

> Constraints:
:::success
* 1 <= `nums.length` <= $2 * 10^4$
* 1 <= `nums[i]`, `k` <= `nums.length`
:::

---

# 解法

## 概念

一樣 sliding window 題目，結果 hard 寫起來跟前幾天差不多，希望是 sliding window 已經掌握住了，話說這幾天寫起來感覺 sliding window 是真的有一個既定的模板啊！

這邊我就一樣 `l` 當標準去走，`r` 先找到第一個適合位置，接著用 `r_` 去找剩下可能解，要說節省下來的時間就是第 12 - 21 行如果 while 能多走就多走，因為 `r` 會趕快跑到後面。或說第 27 - 35 行走越多越吃虧吧！因為到時候都要再換一個 `l` 重走一次

至於為什麼用 dictionary 不用 set，因為在 `freq` 裡面如果出現次數多於 1，那我在處理 `l` 的時候不能直接 remove 掉，這會讓後面出問題，所以我用 dictionary 記憶出現次數，確認都沒有了再 pop 掉

## 程式碼

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        freq = { nums[0]:1 }
        diffCount = 1   # <-- must <= k
        l = 0
        r = 1
        ans = 0
        n = len(nums)

        while l < n:
            # Move right to find fit interval
            while r < n:
                if diffCount == k:
                    break
                elif diffCount < k:
                    if nums[r] in freq:
                        freq[nums[r]] += 1
                    else:
                        freq[nums[r]] = 1
                        diffCount += 1
                    r += 1
            # Increase ans
            if diffCount == k:
                ans += 1

            # Check how long can right move but still fit the interval
            r_ = r
            while r_ < n and diffCount == k:
                if nums[r_] in freq:
                    ans += 1
                    r_ += 1
                else:
                    break
            
            # Modify left
            freq[nums[l]] -= 1
            if freq[nums[l]] == 0:
                freq.pop(nums[l])
                diffCount -= 1
            l += 1

        return ans

---

# 複雜度

## 時間複雜度

雖然是 sliding window，但看程式碼第 27 - 35 行有一段在看 `r` 往後移動多少還是合理範圍，會穰複雜度飆到 $O(n^2)$


## 空間複雜度

因為有 dictionary，所以是 $O(n)$