2537. Count the Number of Good Subarrays

Count the Number of Good Subarrays

題目描述：給定整數陣列 nums 和整數 k。若一個子陣列中相等元素對（i, j，i < j，nums[i] == nums[j]）的數量至少為 k，稱此子陣列為「good subarray」。求 good subarray 的數量。

解題思路（滑動視窗 + 貢獻計數）：

當視窗 [l, r] 內有 pairs 個相等元素對時，所有以 r 為右端點且左端點 ≤ l 的子陣列也都滿足 pairs ≥ k（因為縮短子陣列不會增加對數，但延伸子陣列只會增加）。

關鍵觀察：當 pairs >= k 時，以 r 為右端點、左端點在 [0, l] 之間的所有子陣列也都是 good subarray，共 l + 1 個。

新增元素的貢獻：當 nums[r] 加入視窗時，若 freq[nums[r]] 目前已有 c 個相同元素在視窗中，則新增 c 個新的相等元素對（nums[r] 與每一個既有的 nums[r] 配對）。

演算法：

1. 初始化 freq 頻率表、pairs = 0、l = 0、ans = 0。
2. 右指針 r 向右移動，加入 nums[r]：pairs += freq[nums[r]]；freq[nums[r]]++。
3. 當 pairs >= k 時，縮小左界：freq[nums[l]]--；pairs -= freq[nums[l]]（移除 nums[l] 後，對數減少 freq[nums[l]] 個）；l++。
4. 累加答案：ans += l（以 r 為右端點，左端點可以是 0 到 l-1 共 l 個位置）。

時間複雜度：O(n) — 左右指針各最多移動 n 次，每次操作 O(1)（雜湊表均攤），整體線性。

空間複雜度：O(n) — 頻率表最多儲存 n 個不同元素。

方法二：atMost(k) 轉換

類似 LC 992，定義 atMost(k) = 相等元素對數量 < k 的子陣列數量（即 pairs ≤ k-1）。答案 = 總子陣列數 - atMost(k-1) = n*(n+1)/2 - atMost(k-1)。但此方法需要注意「恰好 < k」等的邊界，不如直接滑動視窗 + l 累加清晰。

方法三：暴力雙重迴圈

枚舉所有子陣列 [l, r]，用頻率表統計相等元素對數，若 ≥ k 則計數。時間 O(n²)，空間 O(n)。當 n = 10⁵ 時超時，僅供驗證。

方法四：前綴對數 + 二分搜尋

定義 prefixPairs[r] = 子陣列 [0, r] 中的相等元素對總數（需減去左側不在視窗的對數）。但此值不具有前綴和的線性可加性（對數的計算依賴整段陣列），難以直接應用，不如滑動視窗直觀。

1. 若 k 等於 0，所有子陣列都是 good subarray，共 n*(n+1)/2 個，上述演算法能否正確處理此邊界情況？需要做什麼修正？
2. 若問題改為「相等元素對數量恰好等於 k」，能否套用 atMost(k) - atMost(k-1) 技巧？請推導出正確的計算公式。
3. 此題的「新增元素貢獻對數 = 目前頻率 c」和「移除元素減少對數 = 移除後頻率」這兩個觀察，本質上是組合數學中 C(c+1,2) - C(c,2) = c 的應用，如何推廣到「三元組相等」的情境？