子数组问题内存超限求助：统计B与C出现次数相等的子数组数量

问题描述 #

给定整数数组A和两个整数B、C，找出其中B出现次数等于C出现次数的非空子数组的数量（空数组不计入统计）。输入为整数数组A、数组长度n1、整数B和C，输出符合条件的子数组数量。

原代码内存超限的原因分析 #

1. 递归栈溢出：原代码用递归枚举所有子数组，子数组总数是O(n²)级别的，当数组长度n较大时，递归调用的深度和次数暴增，函数栈帧不断累积，直接耗尽栈内存导致超限。
2. 不必要的内存浪费：每次递归中都创建局部数组int A[end-start+1]，完全没必要——直接遍历原数组的[start, end]区间就能统计B和C的次数，而且原代码里的拷贝逻辑还存在错误（内层循环重复覆盖整个数组），进一步浪费内存和计算资源。
3. 计数逻辑完全错误：当前递归函数只返回1或0，没有累加所有符合条件的子数组数量，根本无法完成统计任务，同时递归调用时没有接收返回值进行累加，等于白跑了大部分递归流程。

优化解决方案：前缀差+哈希表统计 #

核心思路：把问题转化为前缀差值的统计：

• 遍历数组时，维护一个diff变量，遇到B则+1，遇到C则-1，其他元素不改变diff。
• 对于子数组[i+1, j]，如果diff[j] == diff[i]，说明这个子数组中B和C的出现次数相等。
• 用哈希表记录每个diff值出现的次数，遍历过程中累加当前diff对应的历史出现次数，就是符合条件的子数组数量。

这种方法的时间复杂度是O(n)，空间复杂度是O(n)，完全避免了递归栈溢出和不必要的内存消耗。

修正后的代码 #

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

// 哈希表节点结构
typedef struct HashNode {
    int key;
    int count;
    struct HashNode* next;
} HashNode;

// 哈希表查找或插入节点
HashNode* hashFindOrInsert(HashNode** table, int key, int size) {
    int idx = abs(key) % size;
    HashNode* curr = table[idx];
    while (curr != NULL) {
        if (curr->key == key) {
            return curr;
        }
        curr = curr->next;
    }
    // 插入新节点
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->count = 1;
    newNode->next = table[idx];
    table[idx] = newNode;
    return newNode;
}

// 释放哈希表内存
void freeHashTable(HashNode** table, int size) {
    for (int i = 0; i < size; i++) {
        HashNode* curr = table[i];
        while (curr != NULL) {
            HashNode* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    free(table);
}

int solve(int* A, int n1, int B, int C) {
    int count = 0;
    int diff = 0;
    // 初始化哈希表，初始diff=0出现1次（对应前缀0的情况）
    int hashSize = n1 * 2 + 1; // 防止哈希冲突，设置足够大的大小
    HashNode** hashTable = (HashNode**)calloc(hashSize, sizeof(HashNode*));
    hashFindOrInsert(hashTable, 0, hashSize)->count = 1;

    for (int i = 0; i < n1; i++) {
        if (A[i] == B) {
            diff++;
        } else if (A[i] == C) {
            diff--;
        }
        // 查找当前diff出现的次数，累加到结果
        HashNode* node = hashFindOrInsert(hashTable, diff, hashSize);
        count += node->count - 1; // 减1是因为当前节点刚插入的话count是1，之前的次数是count-1
        node->count++;
    }

    freeHashTable(hashTable, hashSize);
    return count;
}

额外说明 #

• 如果B和C是同一个整数，那么所有非空子数组都符合条件，直接返回n1*(n1+1)/2即可，上述代码也能自动处理这种情况。
• 哈希表的大小可以根据实际情况调整，这里用n1*2+1是为了减少冲突概率，也可以用更高效的哈希实现（比如内置哈希表，如果环境允许）。

内容的提问来源于stack exchange，提问作者driver