題目資訊

題目編號: 2537
題目連結: Count the Number of Good Subarrays
主題: Array, Hash Table, Sliding Window

題目敘述

給定一個整數陣列 nums 和一個整數 k，返回 nums 的* 優良子陣列的數量。

當子陣列 arr 中存在至少 k 對指數 (i, j) 使得 $i < j$ 且 $arr[i] == arr[j]$ 時，該子陣列 arr 被視為優良。

子陣列是陣列中連續的非空元素序列。

範例 1：

輸入: nums = [1,1,1,1,1], k = 10
輸出: 1
解釋: 唯一的優良子陣列是陣列 nums 本身。

範例 2：

輸入: nums = [3,1,4,3,2,2,4], k = 2
輸出: 4
解釋: 有 4 個不同的優良子陣列：
- [3,1,4,3,2,2] 含有 2 對。
- [3,1,4,3,2,2,4] 含有 3 對。
- [1,4,3,2,2,4] 含有 2 對。
- [4,3,2,2,4] 含有 2 對。

約束條件：

$1 \leq nums.length \leq 10^5$
$1 \leq nums[i], k \leq 10^9$

直覺

這個問題要求我們確定連續子陣列的數量，其中至少有 k 對指數 (i, j) 使得 i < j 且 arr[i] == arr[j]。這意味著我們需要找到具有一定重複程度的子陣列。重點在於有效地追蹤這些對的數量，以確定何時一個子陣列成為 “good”。我們注意到，隨著子陣列長度的增加，對的數量只會增加或保持不變，因為更多的元素可能重複。

解法

我們採用雙指針或滑動窗口技術，並結合頻率哈希映射，以追蹤元素的出現並有效地計算當前窗口內的對數。

初始化必要的變數：
- ans，用於存儲 “good” 子陣列的總數，初始為零。
- currentPairs，記錄當前窗口內的對數，初始為零。
- frequency，一個無序的哈希映射，將每個元素對應其在當前窗口中的頻率。
- left，窗口的起始索引，初始為 0。
擴展窗口：
- 使用 right 作為當前窗口的尾端遍歷數組。
- 對於每個元素 nums[right]，透過從哈希映射中獲取 nums[right] 的頻率來更新 currentPairs。這是因為每次出現 nums[right] 都會與其在窗口中的先前出現形成新對。
- 增加 nums[right] 在哈希映射中的頻率。
檢查並收縮窗口：
- 當對數 currentPairs 大於等於 k 且 left 指標小於等於 right 時，執行內部循環：
  - 每個從 left 開始並結束於 right 到 n-1 的子陣列都是 “good”，因為它們滿足對數要求。
  - 因此，將 (n - right) 加入到 ans 中，這代表所有這樣的有效子陣列。
  - 為了探索其他可能的 “good” 子陣列，透過將 left 右移來減小窗口大小：
    - 在哈希映射中減少 nums[left] 的頻率。
    - 透過 nums[left] 的新頻率減少 currentPairs，因為移除一個元素會影響配對計數。
    - 增加 left 以逐步減少窗口大小。
返回結果：
- 完成循環後，ans 包含滿足整個數組條件的 “good” 子陣列的總數。

這種方法有效地遍歷 nums 陣列一次，進行對計數和子陣列評估，其整體時間複雜度相對於數組大小是線性的。這確保在甚至最大限制條件下也能保持最佳性能。

程式碼

C++

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long ans = 0;
        long long currentPairs = 0;
        unordered_map<int, long long> frequency;
        int left = 0;
        int n = nums.size();
        
        for (int right = 0; right < n; ++right) {
            // 每次加入 nums[right] 時，會與其之前出現過的次數形成新的配對。
            currentPairs += frequency[nums[right]];
            frequency[nums[right]]++;
            
            // 如果當前窗口 [left, right] 包含至少 k 個配對，
            // 則從 left 開始並結束於從 right 到 n-1 的每個子陣列都是 "好的"。
            while (currentPairs >= k && left <= right) {
                // 所有從 `left` 開始並以 `right` 結束的子陣列都是有效的。
                ans += (n - right);
                
                // 將 nums[left] 從當前窗口移除，減少配對數。
                frequency[nums[left]]--;
                currentPairs -= frequency[nums[left]];
                ++left;
            }
        }
        
        return ans;
    }
};

Python

class Solution:
    def countGood(self, nums, k):
        ans = 0
        currentPairs = 0
        frequency = {}
        left = 0
        n = len(nums)
        
        for right in range(n):
            # 每次我們加入 nums[right] 時，它會與之前出現的相同元素形成新配對。
            currentPairs += frequency.get(nums[right], 0)
            frequency[nums[right]] = frequency.get(nums[right], 0) + 1
            
            # 如果當前窗口 [left, right] 包含至少 k 個配對，
            # 那麼每個從 left 開始到 right 到 n-1 結束的子陣列都是「良好」的。
            while currentPairs >= k and left <= right:
                # 所有從 `left` 開始到 `right` 的子陣列都是有效的。
                ans += (n - right)
                
                # 從當前窗口移除 nums[left]，減少配對數量。
                frequency[nums[left]] -= 1
                currentPairs -= frequency[nums[left]]
                left += 1
        
        return ans

複雜度分析

時間複雜度: $O(n)$
時間複雜度為 $O(n)$，因為我們使用雙指針技術或滑動窗口方法，這涉及到用 right 和 left 指針迭代遍歷 nums 陣列。對於每個 right 指針的位置，left 指針僅向前移動，保證每個元素在 nums 中被處理的次數是常數次。
具體來說，外層的 for 迴圈通過 right 指針迭代遍歷陣列，並且在這個迴圈中，left 指針控制窗口大小以確保高效地檢查良好組合的數量。內層的 while 迴圈在不重置 left 指針回退的情況下進行迭代，因此保持元素的線性遍歷，確保整體時間複雜度為 $O(n)$。
空間複雜度: $O(n)$
空間複雜度為 $O(n)$，因為我們使用了一個無序映射 (frequency) 來存儲當前窗口中每個元素的計數。在最壞情況下，nums 中的所有元素都是不同的，這將導致映射存儲 n 個元素。因此，所需空間隨輸入大小線性增長。

CS Note
En

Leetcode 2537. Count the Number of Good Subarrays

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析