题目浅析

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

  • 简单地说，就是找出数组中不同数目种类与完全数组一致的子数组数目。

思路分享

  • 先简单说下思路，通过哈希表记录完全数组不同数目的种类，然后就用滑动窗口记录满足条件的子数目，也属于越长越合法的类型。

  • 就是简单不定长滑动窗口的变式，不过看了灵神的题解，发现在简单撰写上，其实还有些方法可以借鉴，比如想要快速统计数组的不同数字，可以直接用数组来初始化set，像是unordered_set<int> st(nums.begin(), nums.end());这样就可以直接用 set 的 size 获得不同数目了。

    https://leetcode.cn/problems/count-complete-subarrays-in-an-array/solutions/2364671/on-hua-dong-chuang-kou-by-endlesscheng-9ztb/

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

  • 参考题解
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
class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        bool rec_type[2001]{};
        int type_count = 0;
        for (const int &i : nums) {
            if (!rec_type[i]) {
                rec_type[i] = true;
                type_count++;
            }
        }
        int left = 0;
        int ans = 0;
        int rec[2001]{};
        int rec_count = 0;
        for (int right = 0; right < nums.size(); right++) {
            rec[nums[right]]++;
            if (rec[nums[right]]==1) {
                rec_count++;
            }
            while(rec_count == type_count) {
                rec[nums[left]]--;
                if (rec[nums[left++]]==0) {
                    rec_count--;
                }
            }
            ans += left;
        }
        return ans;
    }
};