统计完全子数组的数目 图解题解

什么样的连续子数组，才配叫「完全」

子数组是数组里连续的一段。先数出整个数组有多少种不同元素、记成 k；一段连续子数组只要也凑齐这 k 种，就叫完全子数组，要统计的是这种子数组的总个数。题面 nums=[1,3,1,2,2] 不同元素是 1、3、2 共 3 种，答案 4；nums=[5,5,5,5] 只有一种元素、k 为 1，答案 10。

每段都从头数一遍不同元素，账为什么划不来

最直白的做法是把所有子数组都摆出来：起点和终点各挑一个，约 n² 段，每段再从头扫一遍数它有几种不同元素、和 k 比。可每段单独数就要走一趟，三层叠起来是 O(n³)，n 到几千就慢。慢在重复：终点只往右挪一格，前面数过的元素其实一个没变。

集合只增不减，凑齐 k 之后凭什么右边全算

把起点钉住，让右端从它一格格往右伸、元素挨个塞进同一个集合。集合只添不删，不同元素数便只增不减、始终朝一个方向往上爬、绝不回头。

于是集合大小头一回等于 k 时，k 种就全凑齐了。再往右多吞几格，新来的要么是老面孔、要么没有新种类可添，不同元素数只会卡在 k、绝不掉回去。所以从这个终点起、往右每伸一格的更长子数组都照样含齐 k 种、都是完全子数组，一个不漏。窗口一旦完整，右边全算，内层压到一趟扫完。

先把 k 定死，再枚举起点让右端加进集合

先用集合扫全数组求出 k = len(set(nums))，标尺全程不变。外层枚举起点，每换一个起点就把工作集合清空；内层让右端从当前起点往右走、逐个加进集合，大小等于 k 就给答案 ans 加一，之后继续往右扩、每格再判一次。所有起点走完，ans 就是总数。清空是关键：不清则上一轮的元素赖在集合里，大小虚高、把不该算的也算进。

[1,3,1,2,2] 里，这 4 个完全子数组怎么数出来

先求 k：不同元素 1、3、2，共 3 种。起点 0 清空集合，右端依次吞 1→大小 1、3→大小 2、1→大小仍 2、2→{1,3,2} 大小 3 第一次等于 k、ans 记 1；再吞末尾的 2→大小还是 3、ans 到 2。起点 0 数出 [0,3]、[0,4] 两段。

起点 1 清空重来，吞 3→1 种、1→2 种、2→3 种够 k、ans 到 3，再吞 2→仍 3 种、ans 到 4，数出 [1,3]、[1,4]。起点 2 只剩 1、2、2，最多 2 种、凑不齐 3；起点 3、4 元素更少，各数出 0 段。四段相加得 4，和题面答案 4 一致。

拿子数组自己的种类数当标尺，会把每段都误判成完全

最隐蔽的错是搞混标尺数谁的：k 必须是整个数组的不同元素数、算好锁死，若拿每段自己的种类数去比，它永远等于自己，所有子数组都被误判成完全。另两处：换起点忘清空集合，大小会带上一轮的元素虚高；大小刚到 k 就收手不再往右数，会漏掉更长却同样完整的子数组。

复杂度：外层 n 个起点、内层各走一趟、集合加查平均 O(1)，合起来 O(n²)，空间 O(n)。边界：全相同如 [5,5,5,5]，k 为 1，每段都完全、答案就是子数组总数 4×5÷2=10；元素全不同只有整个数组凑得齐 k、答案 1；单元素数组答案也是 1。

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 ans

C++

#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;
    }
}