LeetCode 992: Subarrays with K Different Integers

发表于 | | 阅读次数:
字数统计: 761 | 阅读时长 ≈ 3

题目链接

https://leetcode.com/problems/subarrays-with-k-different-integers/

题意

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。

（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）

返回 A 中好子数组的数目。

示例1:

输出：A = [1,2,1,2,3], K = 2
输入：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例2:

输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

提示:

1.1 <= A.length <= 20000
2.1 <= A[i] <= A.length
3.1 <= K <= A.length

题目类型

滑窗

题目分析

最开始看到这个题目，很自然而然的想到对每个右端点，要找到构成个数刚好为k的最右边的左端点以及刚好为k+1的最右边的左端点，这两者构成的区间长度总和即为我们最后要求的答案。
我最开始的想法是用一个滑窗，用一个map维持滑窗中的整数种类与数目，用堆来维持每种整数最右边的元素位置，堆里的最大值和当前滑窗左端点的区间即为上文所提到的区间。
后面看了题解才发现自己还是太naive了，搞两个滑窗一个维护数目是k的一个维护数目是k+1的就行了。
代码1是用的堆和map，代码2是写了类的两个滑窗的解法。

时间复杂度

$O(N)$

源代码1

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
private:
    map<int, int>mp;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        int i, l = 0;
        int ans = 0;
        mp.clear();
        while (!q.empty())  q.pop();
        for (i = 0; i < A.size(); i++) {
            auto it = mp.find(A[i]);
            if (it == mp.end()) {
                if (mp.size() == K) {
                    // add answer
                    while(!q.empty()) {
                        auto t = q.top(); q.pop();
                        if (mp.find(t.second) != mp.end() && mp[t.second] == t.first) {
                            mp.erase(t.second);
                            l = t.first + 1;
                            break;
                        }
                    }
                }
                mp[A[i]] = i;
            } else
                it -> second = i;
            q.push(make_pair(i, A[i]));
            if (mp.size() == K) {
                while(!q.empty()) {
                    auto t = q.top(); q.pop();
                    if (mp.find(t.second) != mp.end() && mp[t.second] == t.first) {
                        q.push(t);
                        ans += t.first - l + 1;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

源代码2

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Window {
private:
    int count[20002];
    int sz;
public:
    Window() {
        memset(count, 0, sizeof(count));
        sz = 0;
    }
    int get_size() {
        return sz;
    }
    void add(int x) {
        if (count[x] == 0)
            sz++;
        count[x]++;
    }
    void minus(int x) {
        if (count[x] == 1)
            sz--;
        count[x]--;
    }
};
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        int left1 = 0, left2 = 0;
        int ans = 0;
        Window window1, window2;
        for (auto x : A) {
            window1.add(x);
            window2.add(x);
            while (window1.get_size() > K)
                window1.minus(A[left1++]);
            while (window2.get_size() >= K)
                window2.minus(A[left2++]);
            ans += left2 - left1;
        }
        return ans;
    }
};
0%