[LeetCode] 2799. Count Complete Subarrays in an Array JS

內容目錄 隱藏

題目

Let’s say k is the number of distinct elements in the array. Our goal is to find the number of subarrays with k distinct elements.

找出所有包含了整個陣列 nums 所有不同數字的連續子陣列數。

Example 1

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

Example 2

Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

解題思路

這題的 tag 是 Array、Hash Table、Sliding Window

在開始解題之前需要先了解這些概念：

Hash table：類似字典，可以快速地查某個元素有沒有出現過或者出現過幾次。
Sliding Window：用兩個 pointer 移動找出符合的 subarray，常用來處理「子陣列」、「子字串」這種連續範圍的問題。

步驟：

先算出整個陣列的 distinct 數量（用 Set）
- nums = [1,3,1,2,2] distinct set 是 {1,2,3}
雙層迴圈（外層固定 left，內層往右延伸 right）
- 每當 right 擴張到符合條件（目前子陣列的 distinct 數量等於目標），就加上 (n - right + 1)，因為以這個區間開頭、延伸到尾巴的都會是完整子陣列。
- 一旦超過 target 就可以 break（提早結束內層迴圈）

程式碼

var countCompleteSubarrays = function(nums) {
    const totalDistinct = new Set(nums).size; // 總共有幾種不同的數字
    const freq = new Map(); // 記錄目前視窗內每個數字出現的次數
    let left = 0, right = 0, distinct = 0;
    let count = 0;
    const n = nums.length;

    // 每次從不同的 left 開始找完整子陣列
    while (left < n) {
        // right 不斷擴張直到滿足條件
        while (right < n && distinct < totalDistinct) {
            const num = nums[right];
            freq.set(num, (freq.get(num) || 0) + 1);
            if (freq.get(num) === 1) distinct++;
            right++;
        }

        // 如果目前的 window [left, right-1] 已經是完整子陣列，那從 right 到陣列尾巴的每個子陣列也都是完整的，所以可以一次加上 (n - right + 1) 個解
        if (distinct === totalDistinct) {
            count += (n - right + 1);
        }

        // 收縮左邊，準備下次往右推
        const leftNum = nums[left];
        freq.set(leftNum, freq.get(leftNum) - 1);
        if (freq.get(leftNum) === 0) distinct--;
        left++;
    }

    return count;
};

瀏覽量: 6

題目

解題思路

程式碼

相關文章