如何计算数组中奇偶元素数量相等的Odd-Even子数组个数

首先得指出你提供的代码存在几个关键问题，导致它无法正确计算目标子数组的数量：

• 数组越界风险：当j是数组最后一个元素时，arr[j+1]会访问超出数组范围的内存，这会触发未定义行为。
• 逻辑完全偏差：你的代码只遍历了步长为2的子数组，完全忽略了其他长度的可能；而且用sum%2!=0来判断，这和“奇数偶数数量相等”的条件没有直接关联——比如子数组[1,2,3,4]的和是10（偶数），但它的奇偶数量相等，你的代码会漏掉这种情况，反而错误统计一些不符合条件的子数组。

正确的思路：前缀和+哈希表 #

我们可以把问题转化为前缀和问题，这样能把时间复杂度从暴力的O(n²)降到O(n)：

• 把数组中的每个奇数标记为+1，偶数标记为-1。此时，一个子数组的奇偶数量相等，等价于这个子数组的和为0（因为每个奇数贡献+1，偶数贡献-1，数量相等时总和抵消为0）。
• 维护一个前缀和变量，同时用哈希表（或数组，因为前缀和范围固定）记录每个前缀和出现的次数。如果两个不同位置的前缀和相等，说明这两个位置之间的子数组和为0，也就是符合条件的Odd-Even子数组。
• 初始时，前缀和为0的情况要记一次（对应从数组开头到当前位置的子数组和为0的情况）。

正确的C语言实现代码 #

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

int main() {
    int n, i;
    long long count = 0;
    long long prefix_sum = 0;
    
    scanf("%d", &n);
    int arr[n];
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // 前缀和范围是 -n 到 n，用数组做频率表，偏移n处理负数索引
    int *freq = (int *)calloc(2 * n + 1, sizeof(int));
    freq[n] = 1; // 初始前缀和0，对应偏移后的索引n
    
    for (i = 0; i < n; i++) {
        // 更新前缀和：奇数+1，偶数-1
        prefix_sum += (arr[i] % 2 == 1) ? 1 : -1;
        
        // 计算偏移后的索引，避免负数
        int index = prefix_sum + n;
        count += freq[index]; // 累加之前出现过相同前缀和的次数
        freq[index]++; // 更新当前前缀和的出现次数
    }
    
    printf("%lld\n", count);
    free(freq);
    return 0;
}

代码细节解释 #

• 用long long类型：当n很大时（比如1e5），符合条件的子数组数量可能会超过int的取值范围，长整型能避免溢出问题。
• 数组代替哈希表：因为前缀和的取值范围是从-n到n，总共2n+1个可能值，用数组作为频率表比哈希表更高效，通过偏移n把负数索引转化为非负数（比如前缀和-1对应索引n-1，前缀和0对应索引n）。
• 初始freq[n] = 1：对应前缀和为0的初始状态，比如当遍历到某个位置前缀和回到0时，说明从数组开头到该位置的子数组符合条件，这时候初始的次数1会被计入结果。

举个简单例子：数组[1,2,3]

• 前缀和变化：0（初始）→1（1是奇数）→0（2是偶数，1-1=0）→1（3是奇数，0+1=1）
• 遍历过程：
  • 第一个元素后，前缀和1，对应索引1+n，此时频率为0，count保持0，频率更新为1。
  • 第二个元素后，前缀和0，对应索引n，频率为1，count +=1（对应子数组[1,2]），频率更新为2。
  • 第三个元素后，前缀和1，对应索引1+n，频率为1，count +=1（对应子数组[2,3]），最终count为2，和实际符合条件的子数组数量一致。

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