当前位置：首页 > article >正文

LeetCode2799 统计完全子数组的数目

article 2025/1/15 23:32:00

计算完全子数组的数目：从暴力到优化的算法实现

在算法的世界里，常常会遇到各种有趣的数组问题，今天我们要探讨的是计算完全子数组的数目。这个问题来自LeetCode，题目如下：

给你一个由正整数组成的数组 nums。如果数组中的某个子数组满足下述条件，则称之为完全子数组：子数组中不同元素的数目等于整个数组不同元素的数目。我们的任务是返回数组中完全子数组的数目。子数组是数组中的一个连续非空序列。

一、问题分析

1. 基本思路

首先，我们需要理解什么是完全子数组。对于一个数组，我们要找出其中的子数组，并且这些子数组必须满足一个重要条件，即子数组内不同元素的数量等于整个数组中不同元素的数量。

2. 朴素方法

最直观的想法就是使用两层循环来遍历所有可能的子数组。对于每个子数组，我们需要计算其中不同元素的数量。以下是最初的 C 语言实现：

#include <stdio.h>
#include <stdlib.h>

// 计算数组中不同元素的数目
int countDistinct(int* nums, int start, int end) {
    int* visited = (int*)calloc(1001, sizeof(int));  // 假设元素范围是 1 到 1000
    int count = 0;
    for (int i = start; i <= end; i++) {
        if (visited[nums[i]] == 0) {
            visited[nums[i]] = 1;
            count++;
        }
    }
    free(visited);
    return count;
}

// 计算完全子数组的数目
int countCompleteSubarrays(int* nums, int numsSize) {
    int totalDistinct = countDistinct(nums, 0, numsSize - 1);
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            if (countDistinct(nums, i, j) == totalDistinct) {
                count++;
            }
        }
    }
    return count;
}

在 countDistinct 函数中，我们使用了一个 visited 数组来标记元素是否已出现。这个数组假设元素的范围是 1 到 1000，我们遍历 start 到 end 的元素，如果元素未被标记，则标记它并增加 count。

在 countCompleteSubarrays 函数中，我们先计算整个数组的不同元素数量 totalDistinct，然后使用两层循环遍历所有可能的子数组。对于每个子数组，我们调用 countDistinct 函数来计算其不同元素的数量，如果等于 totalDistinct，我们就增加 count 的值。

然而，这种方法的时间复杂度是，因为两层循环和 countDistinct 函数内部的循环，对于较大的数组，性能会变得很差。

3. 遇到的问题

在实际测试中，当输入的数组包含元素大于 1000 时，会出现运行时错误，如

Line 9: Char 20: runtime error: load of address 0x5210000271ac with insufficient space for an object of type 'int' [solution.c]

这是因为我们的 visited 数组大小只考虑了元素范围是 1 到 1000，而实际输入的元素可能超出这个范围，导致了越界访问。

二、优化方案

1. 滑动窗口

为了优化这个问题，我们可以使用滑动窗口的方法。以下是优化后的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>

// 计算数组中不同元素的数目
int countDistinct(int* hashTable, int maxNum) {
    int count = 0;
    for (int i = 1; i <= maxNum; i++) {
        if (hashTable[i] > 0) {
            count++;
        }
    }
    return count;
}

// 计算完全子数组的数目
int countCompleteSubarrays(int* nums, int numsSize) {
    int maxNum = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > maxNum) {
            maxNum = nums[i];
        }
    }
    int* hashTable = (int*)calloc(maxNum + 1, sizeof(int));
    if (hashTable == NULL) {
        fprintf(stderr, "Memory allocation failed for hashTable\n");
        return -1;
    }
    int totalDistinct = 0;
    for (int i = 0; i < numsSize; i++) {
        if (hashTable[nums[i]] == 0) {
            totalDistinct++;
        }
        hashTable[nums[i]]++;
    }
    int count = 0;
    int* windowHashTable = (int*)calloc(maxNum + 1, sizeof(int));
    if (windowHashTable == NULL) {
        fprintf(stderr, "Memory allocation failed for windowHashTable\n");
        free(hashTable);
        return -1;
    }
    int left = 0;
    int windowDistinct = 0;
    for (int right = 0; right < numsSize; right++) {
        if (windowHashTable[nums[right]] == 0) {
            windowDistinct++;
        }
        windowHashTable[nums[right]]++;
        while (windowDistinct == totalDistinct) {
            count += numsSize - right;
            windowHashTable[nums[left]]--;
            if (windowHashTable[nums[left]] == 0) {
                windowDistinct--;
            }
            left++;
        }
    }
    free(hashTable);
    free(windowHashTable);
    return count;
}

2. 优化代码解释

首先，我们遍历数组 nums 找到最大元素 maxNum，这将决定我们需要的 hashTable 和 windowHashTable 的大小。
我们为 hashTable 和 windowHashTable 分配 maxNum + 1 大小的内存，以确保能存储所有元素的出现次数，并对内存分配进行了错误检查。
计算整个数组中不同元素的数目 totalDistinct，存储在 hashTable 中。
我们使用左右指针 left 和 right 来表示滑动窗口。右指针 right 不断向右移动，将元素加入 windowHashTable 并更新 windowDistinct。
当 windowDistinct 等于 totalDistinct 时，说明找到了一个满足条件的子数组，我们更新 count 并移动左指针缩小窗口，同时更新 windowDistinct。