统计完全子数组的数目 图解题解
这道题到底在问什么
- 输入
- nums = [1,3,1,2,2]
- 输出
- 4
- 输入
- nums = [5,5,5,5]
- 输出
- 10
先想最直接的笨办法
记牢这套「先求 k，再枚举起点、右端往右扩，集合凑够 k 就开始逐个计数」，下面每一帧都在套它。（动画第 3 步）
最优解：一步一步想明白
- 3记牢这套「先求 k，再枚举起点、右端往右扩，集合凑够 k 就开始逐个计数」，下面每一帧都在套它。
- 4先扫全数组，不同元素是 1、3、2，一共 k = 3 种。之后每个子数组都要拿它的不同元素个数去和这个 3 比。
- 5起点固定在 0，右端扩到第 0 个 1。这是窗口里的新面孔，不同元素数涨到 1。
- 6窗口不同元素才 1 种，离 k = 3 还差 2 种，这段不算完全子数组，继续把右端往右扩。
- 7起点固定在 0，右端扩到第 1 个 3。这是窗口里的新面孔，不同元素数涨到 2。
- 8窗口不同元素才 2 种，离 k = 3 还差 1 种，这段不算完全子数组，继续把右端往右扩。
- 9起点固定在 0，右端扩到第 2 个 1。它之前已经在窗口里出现过，集合不变，不同元素数还是 2。
- 10窗口不同元素才 2 种，离 k = 3 还差 1 种，这段不算完全子数组，继续把右端往右扩。
- 11起点固定在 0，右端扩到第 3 个 2。这是窗口里的新面孔，不同元素数涨到 3。
- 12窗口不同元素 3 恰好等于 k = 3，[0, 3] 凑齐了全部 3 种，是一个完全子数组，ans 变成 1。
- 13起点固定在 0，右端扩到第 4 个 2。它之前已经在窗口里出现过，集合不变，不同元素数还是 3。
- 14窗口不同元素 3 恰好等于 k = 3，[0, 4] 凑齐了全部 3 种，是一个完全子数组，ans 变成 2。
- 15起点固定在 1，右端扩到第 1 个 3。这是窗口里的新面孔，不同元素数涨到 1。
- 16窗口不同元素才 1 种，离 k = 3 还差 2 种，这段不算完全子数组，继续把右端往右扩。
- 17起点固定在 1，右端扩到第 2 个 1。这是窗口里的新面孔，不同元素数涨到 2。
- 18窗口不同元素才 2 种，离 k = 3 还差 1 种，这段不算完全子数组，继续把右端往右扩。
- 19起点固定在 1，右端扩到第 3 个 2。这是窗口里的新面孔，不同元素数涨到 3。
- 20窗口不同元素 3 恰好等于 k = 3，[1, 3] 凑齐了全部 3 种，是一个完全子数组，ans 变成 3。
- 21起点固定在 1，右端扩到第 4 个 2。它之前已经在窗口里出现过，集合不变，不同元素数还是 3。
- 22窗口不同元素 3 恰好等于 k = 3，[1, 4] 凑齐了全部 3 种，是一个完全子数组，ans 变成 4。
- 23起点 2 从第 2 个数到第 2 个，不同元素最多才 1 种，凑不齐 3 种。起点 2 往后再怎么扩也只有这些元素，这一轮数不出完全子数组。
- 24起点 2 从第 2 个数到第 3 个，不同元素最多才 2 种，凑不齐 3 种。起点 2 往后再怎么扩也只有这些元素，这一轮数不出完全子数组。
- 25起点 2 从第 2 个数到第 4 个，不同元素最多才 2 种，凑不齐 3 种。起点 2 往后再怎么扩也只有这些元素，这一轮数不出完全子数组。
- 26起点 3 从第 3 个数到第 3 个，不同元素最多才 1 种，凑不齐 3 种。起点 3 往后再怎么扩也只有这些元素，这一轮数不出完全子数组。
- 27起点 3 从第 3 个数到第 4 个，不同元素最多才 1 种，凑不齐 3 种。起点 3 往后再怎么扩也只有这些元素，这一轮数不出完全子数组。
- 28起点 4 从第 4 个数到第 4 个，不同元素最多才 1 种，凑不齐 3 种。起点 4 往后再怎么扩也只有这些元素，这一轮数不出完全子数组。
- 29五个起点都枚举完了。起点 0 数到 [0,3]、[0,4] 两个，起点 1 数到 [1,3]、[1,4] 两个，后面三个起点凑不齐 3 种。加起来完全子数组共 4 个。
⚠️ 容易写错的地方
✗ 错：拿子数组自己的不同元素数和自己比
✓ 对：先固定「整个数组」的不同元素数 k 作为标尺
子数组和自己比永远相等，会把所有子数组都误判成完全
✗ 错：换起点时忘了清空集合
✓ 对：每次换起点 i 前把集合清空重来
不清空会把上一个起点的元素带进来，size 虚高
✗ 错：size 到达 k 后就停止计数
✓ 对：size 等于 k 后继续往右扩，每个更长子数组也都计数
已含全部 k 种，再加元素 size 不会变小，仍然完全
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int countCompleteSubarrays(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int cnt = s.size();
int ans = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
s.clear();
for (int j = i; j < n; ++j) {
s.insert(nums[j]);
if (s.size() == cnt) {
++ans;
}
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countCompleteSubarrays(int[] nums) {
Set<Integer> s = new HashSet<>();
for (int x : nums) {
s.add(x);
}
int cnt = s.size();
int ans = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
s.clear();
for (int j = i; j < n; ++j) {
s.add(nums[j]);
if (s.size() == cnt) {
++ans;
}
}
}
return ans;
}
}复杂度
时间
O(n²)
外层枚举起点、内层枚举右端，集合增删查平均 O(1)
空间
O(n)
集合最多装下 n 个不同元素;Python 切片 nums[i:] 另有 O(n) 拷贝但不改量级
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计完全子数组的数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这个 O(n²) 还能优化吗？+
能，用滑动窗口做到 O(n)。固定右端 right，往右加元素;维护一个最左的 left，让 [left, right] 恰好还含齐 k 种(再去掉 nums[left] 就会缺一种)。这时以 right 结尾的完全子数组的左端可以取 0 到 left 的任意位置，共 left 加一个，累加即可。因为右端右移时 left 只会不减，整体一遍扫完就是线性。
它和「至多 K 个不同整数的子数组」是一类题吗？+
是同一族滑动窗口计数题。那类题固定右端、收缩左端来统计满足条件的子数组个数;本题把条件换成「不同元素数等于全局 k」，套路完全相通。认出「固定右端、维护左端边界、按左端可选个数累加」这个母题，一类计数题都能拿下。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计完全子数组的数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。