题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，和一个整数 K，要求返回所有满足条件的子数组数目。条件是子数组内每个数字的数目不超过 K。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int beautifulBouquet(vector<int>& flowers, int cnt) {
        int ans = 0;
        int left = 0;
        unordered_map<int, int> rec;
        for (int right = 0; right < flowers.size(); right++) {
            int index = flowers[right];
            rec[index]++;
            while(rec[index] > cnt) {
                rec[flowers[left++]]--;
            }
            ans += (right-left+1)%1000000007;
            ans %= 1000000007;
        }
        return ans;
    }
};