LeetCode 题解工作台
统计完全子数组的数目
给你一个由 正 整数组成的数组 nums 。 如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ： 子数组中 不同 元素的数目等于整个数组不同元素的数目。 返回数组中 完全子数组 的数目。 子数组 是数组中的一个连续非空序列。 示例 1： 输入： nums = [1,3,1,2,2] 输出：…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们先用哈希表统计数组中不同元素的数目，记为 。 接下来，我们枚举子数组的左端点下标 ，并维护一个集合 ，用于存储子数组中的元素。每次向右移动右端点下标 时，我们将 加入集合 中，并判断集合 的大小是否等于 。如果等于 ，则说明当前子数组是完全子数组，我们将答案增加 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个由 正 整数组成的数组 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 <= 10001 <= nums[i] <= 2000
解题思路
方法一：哈希表 + 枚举
我们先用哈希表统计数组中不同元素的数目，记为 。
接下来，我们枚举子数组的左端点下标 ，并维护一个集合 ，用于存储子数组中的元素。每次向右移动右端点下标 时，我们将 加入集合 中，并判断集合 的大小是否等于 。如果等于 ，则说明当前子数组是完全子数组，我们将答案增加 。
枚举结束后，返回答案即可。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
class Solution:
def countCompleteSubarrays(self, nums: List[int]) -> int:
cnt = len(set(nums))
ans, n = 0, len(nums)
for i in range(n):
s = set()
for x in nums[i:]:
s.add(x)
if len(s) == cnt:
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is added and removed from the hash map at most once. Space complexity is O(n) due to storing counts of elements in the hash map for window tracking. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Tracking distinct elements suggests using a hash map or set.
- question_mark
Sliding window optimization is expected for contiguous subarray counting.
- question_mark
Careful handling of duplicate values inside the window is critical.
常见陷阱
外企场景- error
Failing to adjust the left pointer correctly can lead to overcounting subarrays.
- error
Ignoring that the window must contain exactly all distinct elements causes wrong results.
- error
Not updating the hash map counts properly when sliding the window.
进阶变体
外企场景- arrow_right_alt
Count subarrays with at most k distinct elements instead of exactly k.
- arrow_right_alt
Find the longest complete subarray instead of counting them.
- arrow_right_alt
Compute the number of subarrays missing exactly one distinct element.