LeetCode 1524题解：和为奇数的子数组数目优化

1. 问题背景与核心挑战

遇到LeetCode 1524题时，第一眼看到"和为奇数的子数组数目"这个标题，很多人的直觉反应可能是暴力枚举所有子数组然后检查求和结果。但题目给出的数组长度范围是1 <= arr.length <= 10^5，这意味着O(n^2)的暴力解法必然超时。这道题真正考察的是如何通过数学洞察和前缀和技巧，将时间复杂度优化到O(n)。

子数组问题在算法面试中非常常见，而奇偶性判断这个条件给问题增加了一个有趣的维度。我们需要找到所有满足子数组和为奇数的[i,j]区间组合。在实际编程中，这类问题常出现在数据流分析、金融交易监控等场景，比如统计特定时间段内交易金额总和为奇数的交易区间。

2. 数学建模与关键观察

2.1 奇偶运算的基本性质

解决这个问题的关键在于掌握奇偶数的运算规律：

• 奇数 + 偶数 = 奇数
• 偶数 + 奇数 = 奇数
• 奇数 + 奇数 = 偶数
• 偶数 + 偶数 = 偶数

这个性质可以推广到前缀和数组：假设我们有一个前缀和数组prefix，其中prefix[j] - prefix[i]表示子数组arr[i...j-1]的和。要使这个和为奇数，根据上述性质，prefix[j]和prefix[i]必须具有不同的奇偶性。

2.2 前缀和数组的构建

前缀和数组是解决子数组求和问题的利器。对于数组arr = [1,3,5]，其前缀和数组计算如下：

• prefix[0] = 0
• prefix[1] = prefix[0] + arr[0] = 0 + 1 = 1
• prefix[2] = prefix[1] + arr[1] = 1 + 3 = 4
• prefix[3] = prefix[2] + arr[2] = 4 + 5 = 9

通过观察可以发现，prefix数组的奇偶性变化决定了子数组和的奇偶性。我们需要统计prefix数组中奇数和偶数出现的次数，然后利用组合数学原理计算结果。

3. 动态规划解法实现

3.1 状态定义与转移方程

我们可以用动态规划来记录前缀和的奇偶性统计：

• 定义count[0]表示偶数前缀和的个数
• 定义count[1]表示奇数前缀和的个数
• 初始化count[0] = 1（因为prefix[0]=0是偶数）
• 遍历数组时维护当前前缀和的奇偶性

状态转移方程为：

• 当前前缀和是偶数时，有效子数组数目 += count[1]
• 当前前缀和是奇数时，有效子数组数目 += count[0]

3.2 代码实现与注释

def numOfSubarrays(arr): MOD = 10**9 + 7 count = [1, 0] # count[0]表示偶数前缀和个数，count[1]表示奇数前缀和个数 res = 0 prefix = 0 for num in arr: prefix += num if prefix % 2 == 1: res += count[0] else: res += count[1] count[prefix % 2] += 1 res %= MOD return res

这段代码的精妙之处在于：

1. 只维护前缀和的奇偶性，而不需要存储完整的前缀和数组
2. 通过模2运算快速判断奇偶性
3. 实时更新count数组，确保统计的准确性
4. 每一步都取模防止整数溢出

4. 算法复杂度分析

4.1 时间复杂度

该算法只需要一次线性扫描：

• 遍历数组：O(n)
• 每个元素处理：O(1)的模运算和加法
• 总时间复杂度：O(n)

这比暴力解法的O(n^2)有了质的飞跃，可以轻松处理10^5规模的数据。

4.2 空间复杂度

我们只使用了固定大小的额外空间：

• count数组：O(1)
• 几个临时变量：O(1)
• 总空间复杂度：O(1)

这种空间效率在处理大数据量时尤为重要，避免了内存溢出的风险。

5. 边界条件与特殊测试用例

5.1 常见边界情况

在实现时需要特别注意以下边界条件：

1. 空数组：根据题目约束不会出现
2. 单元素数组：
   • [1] → 有效子数组：1
   • [2] → 有效子数组：0
3. 全奇数数组：[1,3,5] → 有效子数组：4
4. 全偶数数组：[2,4,6] → 有效子数组：0

5.2 大数取模测试

由于结果可能很大，必须确保：

• 每次更新res后立即取模
• 使用10^9+7作为模数
• 测试用例如：[1]*100000，确保不会溢出

6. 同类问题扩展与变种

6.1 和为K的子数组数目

这个问题可以推广到更一般的情况：统计和为K的子数组数目。解法类似但需要使用哈希表记录前缀和出现次数：

def subarraySum(nums, k): from collections import defaultdict prefix_sum = defaultdict(int) prefix_sum[0] = 1 res = 0 current_sum = 0 for num in nums: current_sum += num res += prefix_sum.get(current_sum - k, 0) prefix_sum[current_sum] += 1 return res

6.2 乘积为奇数的子数组数目

如果问题变为统计乘积为奇数的子数组数目，解法会更简单：只需要统计连续奇数的区间，然后计算这些区间的子区间数目。因为只要包含偶数，乘积就会变成偶数。

6.3 二维矩阵中的子矩阵问题

这类前缀和技巧还可以扩展到二维情况，比如统计二维矩阵中满足特定条件的子矩阵数目。这时需要使用二维前缀和数组，原理类似但实现更复杂。

7. 实际工程应用场景

7.1 金融交易分析

在金融领域，这类算法可用于：

• 统计特定时间段内交易金额总和为奇数的交易区间
• 检测异常交易模式（如频繁出现奇数金额的交易组合）

7.2 数据流监控

在实时数据流处理中：

• 监控网络流量中特定模式的子序列
• 检测传感器数据中的异常波动区间

7.3 游戏开发

在游戏逻辑处理中：

• 统计玩家在特定时间段内的得分奇偶性
• 实现特殊成就系统（如连续奇数得分奖励）

8. 优化技巧与注意事项

8.1 位运算优化

在追求极致性能时，可以用位运算代替模运算：

# 代替 prefix % 2 == 1 if prefix & 1: res += count[0] else: res += count[1] count[prefix & 1] += 1

8.2 语言特定优化

在C++等语言中：

• 使用无符号整数避免溢出问题
• 预先分配数组大小减少动态分配开销

8.3 调试技巧

调试时建议：

1. 打印前缀和数组验证正确性
2. 对小规模测试用例手动计算验证
3. 检查边界条件处理是否正确

9. 常见错误与解决方法

9.1 忘记初始化count[0]=1

这是最常见的错误，会导致第一个元素处理不正确。必须记住prefix[0]=0是偶数。

9.2 取模时机不当

应该在每次加法后立即取模，而不是最后统一取模，否则可能在中间步骤就已经溢出。

9.3 奇偶判断错误

混淆prefix[j]和prefix[i]的奇偶性关系，记住：

• 当前前缀和是奇数时，需要之前偶数前缀和的个数
• 当前前缀和是偶数时，需要之前奇数前缀和的个数

10. 进阶学习路径

要深入掌握这类问题，建议：

1. 系统学习前缀和技巧（LeetCode 560、930等题）
2. 掌握动态规划的基本思想
3. 练习更多子数组/子序列问题
4. 学习滑动窗口技巧（与本题无关但常被混淆）
5. 研究位运算在算法中的应用

这类问题的核心在于发现数学规律并将问题转化为已知的模式。在实际面试中，面试官通常会期待看到候选人能够从暴力解法出发，逐步优化到最优解的过程，而不仅仅是给出最终答案。