Problem: 2537. 統計好子數組的數目

思路

滑動窗口

解題過程

思路：

使用滑動窗口來維護子數組，并通過組合計數動態調整滿足條件的數對數目。具體來說，我們維護一個窗口[l,r]，使得窗口內相同元素的對數至少為 k，并計算這樣的窗口數目。

關鍵觀察：

• 當一個元素的頻次從 c 增加到 c+1 時，新增加的數對數目為 c（因為新元素可以與之前的 c 個元素形成 c 對）。

• 當一個元素的頻次從 c 減少到 c-1 時，減少的數對數目為 c-1（因為移除的元素與剩余的 c-1 個元素的數對被移除）。

算法步驟：

• 使用兩個指針 l 和 r 維護滑動窗口，使用哈希表 cnt 記錄元素頻次，使用變量 t 記錄窗口內的數對數目。

• 右指針 r 不斷擴展窗口，更新元素頻次和數對數目 t。

• 當 t >= k 時，嘗試移動左指針 l 縮小窗口，同時更新數對數目 t，直到窗口不再滿足條件。

• 此時，以 r 結尾且滿足條件的子數組數目為 l（即左端點可以是 0 到 l-1 的任意位置）。

Code

python

class Solution:def countGood(self, nums: List[int], k: int) -> int:n = len(nums)ans = 0l = 0cnt = defaultdict(int)  # 記錄數組中的元素頻次t = 0  # 記錄此時窗口的滿足i<j且nums[i]=nums[j]的對數for r, x in enumerate(nums):cnt[x] += 1if cnt[x] >= 2:t += cnt[x] - 1while t >= k and l < r:cnt[nums[l]] -= 1if cnt[nums[l]] >= 1:t -= cnt[nums[l]]l += 1ans += lreturn ans

c++

class Solution {
public:long long countGood(vector<int>& nums, int k) {int n = nums.size();long long ans = 0;int l = 0;unordered_map<int, int> cnt;int t = 0;for (int r = 0; r < n; r++) {cnt[nums[r]]++;if (cnt[nums[r]] >= 2)t += cnt[nums[r]] - 1;while (t >= k && l < r) {cnt[nums[l]]--;if (cnt[nums[l]] >= 1)t -= cnt[nums[l]];l++;}ans += l;}return ans;}
};

復雜度

• 時間復雜度: O(n)

• 空間復雜度: O(n)，用哈希表存儲元素頻次。