12 子数组问题：从枚举到同向双指针

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

前言

「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 12 篇题解，更多题解关注 Somnia1337@力扣。

题目描述

难度：🟡中等

标签：#数组哈希表滑动窗口

子数组是数组中的一个连续非空序列。如果数组中的某个子数组满足下述条件，则称之为 完全子数组：

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

给你一个由正整数组成的数组 nums，返回 nums 中完全子数组的数目。

输入: nums=[1,3,1,2,2]
输出: 4
解释: 完全子数组有: [1,3,1,2],[1,3,1,2,2],[3,1,2],[3,1,2,2]

输入: nums=[5,5,5,5]
输出: 10
解释: 数组仅由元素 5 组成, 所以任意子数组都是完全子数组, 子数组的总数为 10

解题思路

1. 枚举（10ms）

total 表示整个 nums 中不同元素的数目，枚举右端点 r，向左扩展左端点 l，直到子数组中不同元素的数目 cnt == total，此时 l 左侧的下标均可作为左端点。

class Solution {
    public int countCompleteSubarrays(int[] nums) {
	    // 一次遍历, 计算 total
        boolean[] vis = new boolean[2001]; // 1<=nums[i]<=2000
        int total = 0;
        for (int x : nums) {
            if (!vis[x]) total++;
            vis[x] = true;
        }
        
        int ans = 0;
        // 枚举 r, 向左扩展 l
        // 可行性剪枝: r 从 total-1 开始
        for (int r = total - 1; r < nums.length; r++) {
            vis = new boolean[2001];
            int l = r, cnt = 0; // cnt: 子数组中不同元素的数目
            while (l >= 0 && cnt < total) {
                if (!vis[nums[l]]) cnt++;
                vis[nums[l--]] = true;
            }
            if (cnt == total) ans += l + 2; // l 多向左移了 1
        }
        return ans;
    }
}

• 时间复杂度：$O(N^2)$
• 空间复杂度：$O(N)$

2. 同向双指针（2ms）

考虑枚举法的低效部分：随着右端点右移，子数组中不同元素的数目不变/增加，对应的左端点一定不会左移而只会右移，因此可以转化为「同向双指针」。

仍然枚举右端点，但是 cnt 放在 for 外，当 cnt == total 时持续右移 l，此时 l 左侧的下标均可作为左端点。

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        // 一次遍历, 计算 total
        boolean[] vis = new boolean[2001]; // 1<=nums[i]<=2000
        int total = 0;
        for (int x : nums) {
            if (!vis[x]) total++;
            vis[x] = true;
        }
        
        int l = 0, cnt = 0, ans = 0;
        int[] count = new int[2001]; // 子数组中元素的计数, 用于更新 cnt
        // 枚举 r
        for (int r : nums) {
            if (++count[r] == 1) cnt++;
            // 持续 l++
            while (cnt == total) {
                if (--count[nums[l++]] == 0) cnt--;
            }
            ans += l; // l 多向右移了 1
        }
        return ans;
    }
}

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

最后

更多系列「外源推文」&「生活分享」关注公众号：