如何解决数组中的魔法子数组计数问题？现有代码超时求优化

超时原因分析 #

暴力枚举所有子数组并统计奇数个数的解法时间复杂度为O(n²)，当n达到10^{5时，总操作量会突破10}10级别，远超出时间限制，必然导致超时。必须采用线性时间的前缀和+计数思路来优化。

核心思路 #

魔法子数组的定义是「包含非零偶数个奇数的子数组」，可以拆解为：

所有包含偶数个奇数的子数组总数 - 所有全偶数子数组总数（这类子数组的奇数个数为0，不符合「非零」要求）

1. 计算偶数个奇数的子数组总数 #

将原数组转化为0（偶数）和1（奇数）的二进制数组，定义前缀和s[i]为前i个元素中奇数的个数。子数组[j+1, i]的奇数个数为s[i] - s[j]，若该值为偶数，则s[i]与s[j]的奇偶性相同。

统计前缀和中偶数的数量cnt_even和奇数的数量cnt_odd（注意前缀和s[0] = 0，初始时cnt_even = 1），则偶数个奇数的子数组总数为：

total_even = cnt_even * (cnt_even - 1) // 2 + cnt_odd * (cnt_odd - 1) // 2

这是因为从cnt_even个偶数前缀和中任选两个，对应子数组的奇数个数为偶数；同理奇数前缀和的组合也是如此。

2. 计算全偶数子数组总数 #

遍历数组，统计连续偶数段的长度l，每段贡献l*(l+1)//2个全偶数子数组（连续长度为l的序列，子数组数量为l+(l-1)+...+1），累加所有段的贡献得到total_zero。

3. 最终答案 #

魔法子数组数量 = total_even - total_zero

代码实现（Python） #

def count_magic_subarrays(arr):
    cnt_even = 1  # 前缀和s[0]=0，初始为偶数
    cnt_odd = 0
    current_sum = 0
    
    # 统计前缀和奇偶性数量
    for num in arr:
        if num % 2 == 1:
            current_sum += 1
        if current_sum % 2 == 0:
            cnt_even += 1
        else:
            cnt_odd += 1
    
    total_even = cnt_even * (cnt_even - 1) // 2 + cnt_odd * (cnt_odd - 1) // 2
    
    # 统计全偶数子数组数量
    total_zero = 0
    current_length = 0
    for num in arr:
        if num % 2 == 0:
            current_length += 1
        else:
            total_zero += current_length * (current_length + 1) // 2
            current_length = 0
    # 处理最后一段连续偶数
    total_zero += current_length * (current_length + 1) // 2
    
    return total_even - total_zero

# 测试用例1
print(count_magic_subarrays([2,1,2,3]))  # 输出2
# 测试用例2
print(count_magic_subarrays([1,2,5,2,3,7]))  # 输出7

复杂度分析 #

• 时间复杂度：O(n)，仅需两次遍历数组，完全满足n≤10^5的约束。
• 空间复杂度：O(1)，仅使用常数额外空间。

内容的提问来源于stack exchange，提问作者Amal T vinod