Medium

题目描述

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

解题思路

解题思路

这道题要求统计数组中完全子数组的数量，其中完全子数组是指包含数组中所有不同元素的子数组。

主要思路：

  1. 确定目标值：首先统计整个数组中不同元素的个数 k，这是每个完全子数组必须包含的不同元素数量。

  2. 滑动窗口优化：虽然可以暴力枚举所有子数组，但更高效的方法是使用滑动窗口。对于每个右端点 right，找到最小的左端点 left 使得子数组 [left, right] 包含 k 个不同元素。

  3. 计数技巧：一旦找到最小的左端点 left，那么所有以 [0, left] 中任意位置为起点、以 right 为终点的子数组都是完全子数组，这样的子数组有 left + 1 个。

  4. 实现细节：

    • 使用哈希表维护当前窗口中每个元素的出现次数
    • 使用双指针技术，右指针扩展窗口，左指针收缩窗口
    • 当窗口中不同元素个数等于 k 时，尝试收缩左边界找到最小窗口

推荐解法：滑动窗口法，时间复杂度更优。

算法步骤：

  1. 统计数组中不同元素个数 k
  2. 使用滑动窗口遍历数组
  3. 对每个右端点，找到最小左端点使窗口完全
  4. 累加有效的子数组数量

代码实现

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> uniqueElements(nums.begin(), nums.end());
        int k = uniqueElements.size();
        
        int result = 0;
        int left = 0;
        unordered_map<int, int> windowCount;
        
        for (int right = 0; right < n; right++) {
            windowCount[nums[right]]++;
            
            while (windowCount.size() == k) {
                result += n - right;
                windowCount[nums[left]]--;
                if (windowCount[nums[left]] == 0) {
                    windowCount.erase(nums[left]);
                }
                left++;
            }
        }
        
        return result;
    }
};

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        k = len(set(nums))
        
        result = 0
        left = 0
        window_count = {}
        
        for right in range(n):
            window_count[nums[right]] = window_count.get(nums[right], 0) + 1
            
            while len(window_count) == k:
                result += n - right
                window_count[nums[left]] -= 1
                if window_count[nums[left]] == 0:
                    del window_count[nums[left]]
                left += 1
        
        return result

public class Solution {
    public int CountCompleteSubarrays(int[] nums) {
        int n = nums.Length;
        var uniqueElements = new HashSet<int>(nums);
        int k = uniqueElements.Count;
        
        int result = 0;
        int left = 0;
        var windowCount = new Dictionary<int, int>();
        
        for (int right = 0; right < n; right++) {
            if (windowCount.ContainsKey(nums[right])) {
                windowCount[nums[right]]++;
            } else {
                windowCount[nums[right]] = 1;
            }
            
            while (windowCount.Count == k) {
                result += n - right;
                windowCount[nums[left]]--;
                if (windowCount[nums[left]] == 0) {
                    windowCount.Remove(nums[left]);
                }
                left++;
            }
        }
        
        return result;
    }
}

var countCompleteSubarrays = function(nums) {
    const totalDistinct = new Set(nums).size;
    let count = 0;
    
    for (let i = 0; i < nums.length; i++) {
        const seen = new Set();
        for (let j = i; j < nums.length; j++) {
            seen.add(nums[j]);
            if (seen.size === totalDistinct) {
                count += nums.length - j;
                break;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
滑动窗口O(n)O(k)

其中：

  • n 是数组长度
  • k 是数组中不同元素的个数
  • 滑动窗口解法中，每个元素最多被访问两次（一次加入窗口，一次移出窗口）
  • 空间复杂度主要用于存储哈希表，最多存储 k 个不同元素

相关题目