題目資訊

題目編號: 2799
題目連結: Count Complete Subarrays in an Array
主題: Array, Hash Table, Sliding Window

題目敘述

你有一個由正整數組成的陣列 nums。

如果滿足以下條件，我們稱該陣列的一個子陣列為完整：

子陣列中不同元素的數量等於整個陣列中不同元素的數量。

返回 完整子陣列的數量 。

子陣列 是陣列中連續的非空部分。

範例 1:

輸入: nums = [1,3,1,2,2]
輸出: 4
解釋: 完整的子陣列如下: [1,3,1,2], [1,3,1,2,2], [3,1,2] 和 [3,1,2,2]。

範例 2:

輸入: nums = [5,5,5,5]
輸出: 10
解釋: 陣列只包含整數 5，因此任何子陣列都是完整的。我們可以選擇的子陣列數量是 10。

約束條件:

$1 \leq \text{nums.length} \leq 1000$
$1 \leq \text{nums}[i] \leq 2000$

直覺

解決這個問題的主要想法是找出在給定陣列 nums 中，包含全部獨特元素的子陣列。關鍵觀察點在於追蹤子陣列中的獨特元素數量，這可以透過滑動窗口技巧結合用於快速更新和查詢獨特元素計數的資料結構（如映射或集合）來高效地實現。

解法

該解法使用一個雙指標滑動窗口的方法來達成。具體步驟如下：

初始化：
- 使用 set 計算整個陣列中獨特元素的總數，它會自動過濾重複的元素。
- 初始化兩個指標，left 和 right，表示當前滑動窗口的邊界。將兩個指標都設置在陣列的開始處。
- 使用一個整數變數 currentDistinct 來追蹤當前窗口內獨特元素的數量。
- 使用一個映射 count 來記錄當前窗口內每個元素的出現次數。
滑動窗口擴展：
- 逐步移動 right 指標來擴展窗口，將當前元素 nums[right] 加入窗口。
- 如果這個元素是首次引入到窗口中（即在映射中的計數先前為零），則增加 currentDistinct。
滑動窗口收縮：
- 如果有重複元素，具體來說，即當 nums[left] 的計數大於一時，則移動 left 指標以縮小窗口，並減少其計數。
計算完整子陣列：
- 當調整窗口使得 currentDistinct 與總獨特元素數相符後，計算可能的子陣列數量。這是由當前 left 指標的位置加一給出，因為從 left 到 right 的任何較小子陣列也將是完整的。
- 將此數量加到 answer 中。
迭代直到完成：
- 不斷通過移動 right 指標來擴展窗口，直到遍歷整個陣列。
結果：
- 在迴圈結束後累積的 answer 就是完整子陣列的總數。

通過遵循這些步驟，每個滿足條件的子陣列都將被有效地計數，確保演算法在給定問題約束條件下維持在可接受的時間複雜度範圍內。

程式碼

C++

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        // 使用集合初始化所有來自陣列的不重複元素
        set<int> distinctSet(nums.begin(), nums.end());

        // 初始化滑動視窗技術的指標和變數
        int left = 0, right = 0, answer = 0;
        int len = nums.size();
        int totalDistinct = distinctSet.size();
        int currentDistinct = 0;
        
        // 映射來追蹤當前視窗中元素的計數
        map<int, int> count;

        // 遍歷陣列，'right' 指向視窗的結束
        for (; right < len; right++) {
            // 增加當前元素的計數
            // 如果此元素第一次出現，增加不重複計數
            if (++count[nums[right]] == 1) {
                currentDistinct++;
            }

            // 如果一個元素出現多次，增加 'left' 以減少視窗大小
            while (count[nums[left]] > 1) {
                count[nums[left++]]--;
            }

            // 如果視窗中的不重複元素數量等於總不重複元素數量
            // 將能夠由當前視窗形成的子陣列數量加入答案中
            if (totalDistinct == currentDistinct) {
                answer += left + 1;
            }
        }
        
        return answer;
    }
};

Python

class Solution:
    def countCompleteSubarrays(self, nums):
        # 初始化一個集合，包含陣列中所有不同的元素
        distinctSet = set(nums)

        # 初始化滑動窗口技術所需的指標和變數
        left = 0
        right = 0
        answer = 0
        length = len(nums)
        totalDistinct = len(distinctSet)
        currentDistinct = 0
        
        # 字典用來記錄當前窗口中元素的計數
        count = {}

        # 遍歷陣列，'right' 指示窗口的結尾
        while right < length:
            # 增加當前元素的計數
            # 如果該元素是第一次出現，增加不同元素的計數
            if nums[right] in count:
                count[nums[right]] += 1
            else:
                count[nums[right]] = 1
            
            if count[nums[right]] == 1:
                currentDistinct += 1

            # 當元素出現多於一次時，縮小窗口尺寸
            while count[nums[left]] > 1:
                count[nums[left]] -= 1
                left += 1

            # 如果窗口中不同元素的數量等於總的不同元素數量
            # 將可以用當前窗口形成的子陣列數量加入答案
            if totalDistinct == currentDistinct:
                answer += left + 1
            
            right += 1
        
        return answer

複雜度分析

時間複雜度: 此解法的時間複雜度為 $O(n)$，其中 $n$ 是輸入陣列 nums 的長度。這是因為演算法使用滑動窗口技術配合兩個指標 left 和 right 進行單次遍歷。每個元素最多會被處理兩次，第一次是當 right 指標把它包含進窗口時，第二次則可能是當 left 指標把它從窗口排除時。
空間複雜度: 此解法的空間複雜度在最壞情況下為 $O(n)$，主要歸因於 count 映射，如果所有元素不重複的話，可能需要單獨儲存輸入陣列的每一個元素。此外，最初使用一個集合來儲存來自陣列的各個不同元素，且若所有元素都是唯一的，這個集合也可能包含陣列中的每一個元素。因此，總體的空間使用量與輸入的大小成線性關係。

CS Note
En

Leetcode 2799. Count Complete Subarrays in an Array

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析