題目描述:給定整數陣列 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) 但常數更小。
1. Define atMost(nums, k):
a. freq = {}, l = 0, distinct = 0, count = 0.
b. For r in 0..n-1:
- If freq[nums[r]] == 0: distinct++.
- freq[nums[r]]++.
- While distinct > k:
* freq[nums[l]]--; if == 0: distinct--.
* l++.
- count += r - l + 1.
c. Return count.
2. Return atMost(nums, k) - atMost(nums, k - 1).維護兩個左指針 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 簡潔。
將問題分成左半段和跨中點的情況分別計算,但滑動視窗在此問題上已是最優,分治只會增加常數且邏輯複雜,無實際優勢。
atMost 技巧可否直接推廣?推導公式是什麼?nums[i] 的值域極大(如 10⁹),使用 unordered_map 的雜湊碰撞可能影響效能,如何改用有序 map 或座標壓縮來保證最壞情況時間複雜度?atMost(k) - atMost(k-1) 技巧在 LC 1248(Count Number of Nice Subarrays)和 LC 2537 中也有應用,這三題的共同抽象模式是什麼?