给你一个由 正 整数组成的数组 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

思路分析

暴力+哈希

时间复杂度 O()

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = len(set(nums))
        res = 0
        for i in range(n):
            se = set()
            for j in range(i,n):
                if nums[j] not in se:
                    se.add(nums[j])
                if len(se) == cnt:
                    res+=1
        return res

滑动窗口

时间复杂度 O()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        l,r = 0,0
        n = len(nums)
        m = len(set(nums))
        res = 0
        diff = 0
        d = dict()
        while l < n:
            while r < n and diff < m:
                d[nums[r]] = d.get(nums[r],0) + 1
                if d[nums[r]] == 1:
                    diff +=1
                r += 1
            # 跳出来了
            if diff < m:
                break
            res += n - r + 1
            d[nums[l]] -= 1
            if d[nums[l]] == 0:
                diff -= 1
            l+=1
        return res

雪景式

暴力

暴力的做法，先固定左端点，然后模拟往集合里面加数字即可，当集合长度等于整个数组不同元素的数目时，无需接着遍历，后面的子数组都满足答案要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        le = len(set(nums))
        ans = 0
        for i in range(n):
            s = set()
            for j in range(i,n):
                s.add(nums[j])
                if len(s) == le:
                    ans += n - j
                    break
        return ans

滑动窗口

固定右端点，尽可能大的把左端点移动，答案的贡献个数就是左边移动的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        l,ans = 0,0
        le = len(set(nums))
        c = Counter()
        for r in range(n):
            c[nums[r]] += 1
            while c[nums[l]] > 1:
                c[nums[l]] -= 1
                l += 1
            if len(c) == le:
                ans += l + 1
        return ans

灵神

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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]
            ans += left  # 子数组左端点 < left 的都是合法的
            cnt[v] += 1
            while len(cnt) == m:
                ans += 1  # 子数组左端点等于 left 是合法的
                x = nums[left]
                cnt[x] -= 1
                if cnt[x] == 0:
                    del cnt[x]
                left += 1
        return ans

相似题目

LC992. K 个不同整数的子数组