992. Subarrays with K Different Integers

Subarrays with K Different Integers

題目描述：給定整數陣列 nums 和整數 k，求恰好有 k 個不同整數的子陣列數量。

解題思路（atMost(k) - atMost(k-1) 技巧）：

直接用滑動視窗維護「恰好 k 個不同整數」較為困難（視窗的右邊界移動時難以維護精確計數）。關鍵觀察：

恰好 k 個 = 最多 k 個 - 最多 k-1 個

定義 atMost(k) = 最多有 k 個不同整數的子陣列數量，則答案 = atMost(k) - atMost(k-1)。

atMost(k) 的滑動視窗實作：

• 維護左指針 l、右指針 r、頻率表 freq、視窗內不同整數數量 distinct。
• 右指針向右移動，加入 nums[r]，更新 freq 和 distinct。
• 若 distinct > k：移動左指針直到 distinct <= k（從 freq 表中移除 nums[l]，若頻率降為 0 則 distinct--）。
• 當前以 r 為右端點的合法子陣列數量為 r - l + 1（左端點可以是 l 到 r 之間任意位置）。
• 累加所有 r 的貢獻。

兩次 atMost 呼叫，線性時間完成。

時間複雜度：O(n) — atMost 函式中左右指針各最多移動 n 次，整體為 O(n)；呼叫兩次仍為 O(n)。

空間複雜度：O(n) — 雜湊表最多儲存 n 個不同元素（陣列元素值域最大 n）。若元素值域有限（如題目保證 1 ≤ nums[i] ≤ n），可改用固定大小陣列降至 O(n) 但常數更小。

方法二：單次滑動視窗（雙左指針）

維護兩個左指針 l1 和 l2：l1 是「恰好 k 個不同」的最左可行左界，l2 是「最多 k 個不同」的最左可行左界。每個 r 貢獻 l2 - l1 個以 r 結尾的恰好 k 個不同子陣列。時間 O(n)，空間 O(k)，只需一次線性掃描，常數較 atMost 差法略優（省一次掃描），但邏輯較複雜。

方法三：前綴計數 + 雜湊表

對每個右端點 r，記錄 prefix[r] = 以 r 結尾的最長 ≤ k 個不同子陣列的左界，再透過差分計算恰好 k 個的數量。本質上與 atMost 方法等價，只是用陣列儲存中間狀態，空間 O(n)，不如直接呼叫兩次 atMost 簡潔。

方法四：分治法

將問題分成左半段和跨中點的情況分別計算，但滑動視窗在此問題上已是最優，分治只會增加常數且邏輯複雜，無實際優勢。

1. 若問題改為「至少有 k 個不同整數的子陣列數量」，atMost 技巧可否直接推廣？推導公式是什麼？
2. 若 nums[i] 的值域極大（如 10⁹），使用 unordered_map 的雜湊碰撞可能影響效能，如何改用有序 map 或座標壓縮來保證最壞情況時間複雜度？
3. 此題的 atMost(k) - atMost(k-1) 技巧在 LC 1248（Count Number of Nice Subarrays）和 LC 2537 中也有應用，這三題的共同抽象模式是什麼？