2799-统计完全子数组的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个由 正 整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

  • 子数组中 不同 元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

示例 1：

**输入：** nums = [1,3,1,2,2]
**输出：** 4
**解释：** 完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。

示例 2：

**输入：** nums = [5,5,5,5]
**输出：** 10
**解释：** 数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2000

下午两点【b站@灵茶山艾府】 直播讲题，欢迎关注！

经典滑窗，视频讲解可以看【基础算法精讲 01】 。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        m = len(set(nums))
        cnt = Counter()
        ans = left = 0
        for v in nums:  # 枚举子数组右端点 v=nums[i]
            cnt[v] += 1
            while len(cnt) == m:
                x = nums[left]
                cnt[x] -= 1
                if cnt[x] == 0:
                    del cnt[x]
                left += 1
            ans += left  # 子数组左端点 < left 的都是合法的
        return ans
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int countCompleteSubarrays(int[] nums) {
        var set = new HashSet<Integer>();
        for (int x : nums) set.add(x);
        int m = set.size();
        var cnt = new HashMap<Integer, Integer>();
        int ans = 0, left = 0;
        for (int v : nums) { // 枚举子数组右端点 v=nums[i]
            cnt.merge(v, 1, Integer::sum);
            while (cnt.size() == m) {
                int x = nums[left++];
                if (cnt.merge(x, -1, Integer::sum) == 0)
                    cnt.remove(x);
            }
            ans += left; // 子数组左端点 < left 的都是合法的
        }
        return ans;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countCompleteSubarrays(vector<int> &nums) {
        int m = unordered_set<int>(nums.begin(), nums.end()).size();
        unordered_map<int, int> cnt;
        int ans = 0, left = 0;
        for (int v: nums) { // 枚举子数组右端点 v=nums[i]
            cnt[v]++;
            while (cnt.size() == m) {
                int x = nums[left++];
                if (--cnt[x] == 0)
                    cnt.erase(x);
            }
            ans += left; // 子数组左端点 < left 的都是合法的
        }
        return ans;
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func countCompleteSubarrays(nums []int) (ans int) {
	set := map[int]struct{}{}
	for _, v := range nums {
		set[v] = struct{}{}
	}
	m := len(set)

	cnt := map[int]int{}
	left := 0
	for _, v := range nums { // 枚举子数组右端点 v=nums[i]
		cnt[v]++
		for len(cnt) == m {
			x := nums[left]
			cnt[x]--
			if cnt[x] == 0 {
				delete(cnt, x)
			}
			left++
		}
		ans += left // 子数组左端点 < left 的都是合法的
	}
	return
}
[sol-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var countCompleteSubarrays = function (nums) {
    const m = new Set(nums).size;
    let cnt = new Map();
    let ans = 0, left = 0;
    for (const v of nums) { // 枚举子数组右端点 v=nums[i]
        cnt.set(v, (cnt.get(v) ?? 0) + 1);
        while (cnt.size === m) {
            const x = nums[left++];
            cnt.set(x, cnt.get(x) - 1);
            if (cnt.get(x) === 0)
                cnt.delete(x);
        }
        ans += left; // 子数组左端点 < left 的都是合法的
    }
    return ans;
};

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 nums 的长度。
  • 空间复杂度：\mathcal{O}(n)。

相似题目

 Comments
On this page
2799-统计完全子数组的数目