992. K 個不同整數的子數組

推薦事前閱讀：滑動窗口

思路

題目要求一在一個數組當中，恰好包含 $k$ 個不同數字的子數組有幾個。
比如 $[1,2,3,1,2],k=3$ ，滿足條件的子數組有 $[1,2,3],~[1,2,3,1],~[1,2,3,1,2]\dots$ 。

題目可以拆成兩個小問題，定義一個函數f(nums, k)能找到nums中包含 $k$ 或以下不同數字的子數組， 原先的問題就能拆成f(nums, k) - f(nums, k - 1)。
這個小問題就比較簡單了，每次滑動窗口往右延伸之後，盡量不要縮減左邊界，
然後計算以當前 $j$ 為結尾的字串數量，從 $i\sim{j}$ 的所有位置都可以做為起點。
因為既然 $nums[i\dots{j}]$ 都滿足條件了，那麼更短的 $nums[i+1\dots{j}],~nums[i+2\dots{j}],~\dots$ 就更滿足條件了。

程式碼

滑動窗口

class Solution {
private:
    int f(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> freq;
        int unique_cnt = 0, res = 0;
        for(int i = 0, j = 0; j < n; j++) {
             if(++freq[nums[j]] == 1) {
                unique_cnt++;
             }
             while(unique_cnt > k) { // 太多不同的數字，不得已縮減左邊界
                 if(--freq[nums[i++]] == 0) {
                     unique_cnt--;
                 }
             }
             res += j - i + 1; // nums[i...j], 一共有 j - i 個以 j 結尾的子字串
        }
        return res;
    }
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return f(nums, k) - f(nums, k - 1);
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$