跳转至

K 个不同整数的子数组⚓︎

Leetcode题目链接

描述⚓︎

详见中文题目链接。

解答⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
private:
    int numOfMostKDistinct(vector<int>& nums, int k) {
        int n = nums.size();
        int res = 0, kinds = 0;
        vector<int> cnts(2e4+1, 0);

        for (int left = 0, right = 0; right < n; right++) {
            if (++cnts[nums[right]] == 1) kinds++;

            while (kinds > k) {
                if (--cnts[nums[left++]] == 0) {
                    kinds--;
                }
            }
            res += right - left + 1;
        }
        return res;
    }

public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return numOfMostKDistinct(nums, k) - numOfMostKDistinct(nums, k - 1);
    }
};