LeetCode2799 统计完全子数组的数目
计算完全子数组的数目：从暴力到优化的算法实现
在算法的世界里，常常会遇到各种有趣的数组问题，今天我们要探讨的是计算完全子数组的数目。这个问题来自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。
三、时间复杂度分析
使用滑动窗口后，时间复杂度得到了显著优化。因为左右指针最多遍历数组一次，所以时间复杂度从 降低到了
。
四、总结
这个问题展示了如何从一个简单的暴力算法逐步优化到一个更高效的算法。在处理数组问题时，滑动窗口是一个非常强大的工具，它可以帮助我们避免不必要的重复计算，提高算法的效率。同时，对于内存分配和数组范围的考虑也很重要，确保代码在处理各种输入时都能稳定运行。
在实际编程中，我们需要时刻关注可能出现的边界情况和性能瓶颈，像这里的元素范围和内存分配问题，都是需要注意的细节。
原文地址：https://blog.csdn.net/qq_64604732/article/details/145141823
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！