1. 问题背景与核心挑战今天遇到一道很有意思的LeetCode题目1524题要求计算数组中所有和为奇数的子数组数量。初看题目似乎简单但仔细思考后发现其中蕴含着几个需要巧妙处理的算法问题。给定一个整数数组arr我们需要统计所有可能的连续子数组中元素之和为奇数的个数。由于子数组数量随数组长度呈平方级增长长度为n的数组有n*(n1)/2个子数组直接暴力计算在n较大时比如1e5必然超时。这就要求我们找到更高效的数学规律或算法优化手段。2. 暴力解法与时间复杂度分析先来看最直观的暴力解法这能帮助我们理解问题本质def numOfSubarrays(arr): count 0 n len(arr) for i in range(n): current_sum 0 for j in range(i, n): current_sum arr[j] if current_sum % 2 1: count 1 return count这个双重循环的时间复杂度是O(n²)当n1e5时操作次数将达到1e10量级远超一般算法题的时间限制通常要求1e6-1e8次操作内。因此必须寻找更优解。3. 数学规律与前缀和优化观察到一个关键数学性质奇数偶数奇数偶数奇数奇数其他组合均为偶数。这意味着当前缀和S[j]是奇数时我们需要找到之前偶数前缀和S[i]的数量当前缀和S[j]是偶数时我们需要找到之前奇数前缀和S[i]的数量基于此可以维护两个计数器odd_cnt记录奇数前缀和的数量even_cnt记录偶数前缀和的数量初始化时空子数组的和为0偶数所以even_cnt1odd_cnt0。4. 动态规划解法实现以下是基于前缀和与计数器的优化解法def numOfSubarrays(arr): MOD 10**9 7 prefix 0 odd even 0 even 1 # 初始空子数组和为0偶数 res 0 for num in arr: prefix num if prefix % 2 1: res even odd 1 else: res odd even 1 res % MOD return res这个算法的时间复杂度是O(n)空间复杂度是O(1)完美解决了大规模数据的问题。5. 关键点解析与边界处理有几个需要特别注意的细节MOD运算的位置题目要求结果对1e97取模应该在每次累加res后立即取模而不是最后统一取模防止中间结果溢出。初始条件设置even初始化为1对应空子数组的情况这是很多同学容易忽略的边界条件。奇偶性判断优化可以用位运算prefix 1代替prefix % 2效率更高。负数处理Python中负数取模结果与数学定义一致但其他语言可能需要额外处理。例如在C中int mod prefix % 2; if(mod 0) mod 2;6. 算法正确性验证让我们用一个简单例子验证算法输入arr [1,3,5]初始prefix0, even1, odd0, res0处理1prefix1(奇), reseven1, odd1 → res1处理3prefix4(偶), resodd1, even2 → res2处理5prefix9(奇), reseven2, odd2 → res4实际子数组[1], [3,5], [1,3,5], [5] 共4个和为奇数的子数组验证通过。7. 性能对比与优化空间对比两种解法的性能差异数据规模暴力解法前缀和解法n100~5ms~0.1msn1e4~500ms~1msn1e5超时~10ms进一步优化方向使用位运算代替取模循环展开对于特别大的n并行计算前缀和对于多核系统8. 同类问题扩展掌握这个技巧后可以解决一系列类似问题和为K的倍数的子数组数目LeetCode 974乘积为奇数的子数组数目最长和为奇数的子数组长度例如解决乘积为奇数的问题时只需统计全奇数的子数组因为只要包含一个偶数乘积就会变偶数。此时问题转化为统计连续奇数的片段。9. 常见错误与调试技巧在实现这类算法时容易犯的几个错误初始条件错误忘记初始化even1导致少计数空子数组情况更新顺序错误应该先计算结果再更新计数器顺序颠倒会导致错误整数溢出未及时取模导致中间结果溢出尤其在C/Java中负数处理不当如前所述负数取模需要特别处理调试时可以打印每一步的前缀和与计数器状态用小规模数据手工验证对比暴力解法的结果10. 实际应用场景这类算法在实际中有广泛应用金融分析统计满足特定条件的连续交易区间信号处理寻找满足能量特征的信号片段基因组学分析DNA序列中满足碱基组合规律的区段例如在股票分析中可能需要统计连续N天累计涨幅为奇数的时段就可以直接套用这个算法框架。11. 语言特性注意事项在不同编程语言中实现时需注意Python整数不会溢出取模结果总是与数学定义一致但大数运算较慢必要时可用PyPy加速C/Java必须及时取模防止溢出负数取模需要额外处理可以用位运算优化JavaScript数字都是浮点数但位运算会转为32位整数大数需要用BigInt12. 进阶思考与挑战对于想进一步挑战的同学可以尝试空间复杂度能否进一步优化已经O(1)了如果要求同时统计奇数和、偶数和的子数组数量如何修改如果数组可以动态变化增加/删除元素如何维护统计结果线段树应用例如问题2的解法def countSubarrays(arr): prefix 0 cnt [1, 0] # cnt[0] for even, cnt[1] for odd res [0, 0] # res[0] for even, res[1] for odd for num in arr: prefix num mod prefix % 2 res[mod] cnt[0] res[1-mod] cnt[1] cnt[mod] 1 return res # [even_count, odd_count]13. 算法竞赛中的应用技巧在编程竞赛中处理此类问题的经验快速识别问题类型看到连续子数组和要立即想到前缀和模数处理技巧通常题目要求对1e97取模要养成及时取模的习惯测试用例设计自己构造边界用例如全奇数、全偶数、空数组等模板化代码可以准备前缀和的代码模板快速套用14. 学习资源推荐想深入掌握这类算法的同学可以参考《算法导论》第4章 - 分治策略与递归式LeetCode前缀和标签下的经典题目和为K的子数组和可被K整除的子数组和等于k的最长子数组长度竞赛选手的博客如Codeforces上的前缀和技巧分享15. 个人解题心得在解决这个问题时我经历了几个关键突破点最初尝试用滑动窗口但发现窗口性质不满足单调性要求然后想到前缀和但一开始忽略了利用奇偶性质的优化通过具体例子如[1,3,5]手工计算发现了奇偶计数的规律调试时发现初始条件设置错误通过打印中间状态找到问题最大的收获是对于统计类问题寻找不变量或数学规律往往比直接计算更高效。前缀和配合奇偶计数将O(n²)问题降为O(n)这种优化思路值得牢记。
1. 问题背景与核心挑战今天遇到一道很有意思的LeetCode题目1524题要求计算数组中所有和为奇数的子数组数量。初看题目似乎简单但仔细思考后发现其中蕴含着几个需要巧妙处理的算法问题。给定一个整数数组arr我们需要统计所有可能的连续子数组中元素之和为奇数的个数。由于子数组数量随数组长度呈平方级增长长度为n的数组有n*(n1)/2个子数组直接暴力计算在n较大时比如1e5必然超时。这就要求我们找到更高效的数学规律或算法优化手段。2. 暴力解法与时间复杂度分析先来看最直观的暴力解法这能帮助我们理解问题本质def numOfSubarrays(arr): count 0 n len(arr) for i in range(n): current_sum 0 for j in range(i, n): current_sum arr[j] if current_sum % 2 1: count 1 return count这个双重循环的时间复杂度是O(n²)当n1e5时操作次数将达到1e10量级远超一般算法题的时间限制通常要求1e6-1e8次操作内。因此必须寻找更优解。3. 数学规律与前缀和优化观察到一个关键数学性质奇数偶数奇数偶数奇数奇数其他组合均为偶数。这意味着当前缀和S[j]是奇数时我们需要找到之前偶数前缀和S[i]的数量当前缀和S[j]是偶数时我们需要找到之前奇数前缀和S[i]的数量基于此可以维护两个计数器odd_cnt记录奇数前缀和的数量even_cnt记录偶数前缀和的数量初始化时空子数组的和为0偶数所以even_cnt1odd_cnt0。4. 动态规划解法实现以下是基于前缀和与计数器的优化解法def numOfSubarrays(arr): MOD 10**9 7 prefix 0 odd even 0 even 1 # 初始空子数组和为0偶数 res 0 for num in arr: prefix num if prefix % 2 1: res even odd 1 else: res odd even 1 res % MOD return res这个算法的时间复杂度是O(n)空间复杂度是O(1)完美解决了大规模数据的问题。5. 关键点解析与边界处理有几个需要特别注意的细节MOD运算的位置题目要求结果对1e97取模应该在每次累加res后立即取模而不是最后统一取模防止中间结果溢出。初始条件设置even初始化为1对应空子数组的情况这是很多同学容易忽略的边界条件。奇偶性判断优化可以用位运算prefix 1代替prefix % 2效率更高。负数处理Python中负数取模结果与数学定义一致但其他语言可能需要额外处理。例如在C中int mod prefix % 2; if(mod 0) mod 2;6. 算法正确性验证让我们用一个简单例子验证算法输入arr [1,3,5]初始prefix0, even1, odd0, res0处理1prefix1(奇), reseven1, odd1 → res1处理3prefix4(偶), resodd1, even2 → res2处理5prefix9(奇), reseven2, odd2 → res4实际子数组[1], [3,5], [1,3,5], [5] 共4个和为奇数的子数组验证通过。7. 性能对比与优化空间对比两种解法的性能差异数据规模暴力解法前缀和解法n100~5ms~0.1msn1e4~500ms~1msn1e5超时~10ms进一步优化方向使用位运算代替取模循环展开对于特别大的n并行计算前缀和对于多核系统8. 同类问题扩展掌握这个技巧后可以解决一系列类似问题和为K的倍数的子数组数目LeetCode 974乘积为奇数的子数组数目最长和为奇数的子数组长度例如解决乘积为奇数的问题时只需统计全奇数的子数组因为只要包含一个偶数乘积就会变偶数。此时问题转化为统计连续奇数的片段。9. 常见错误与调试技巧在实现这类算法时容易犯的几个错误初始条件错误忘记初始化even1导致少计数空子数组情况更新顺序错误应该先计算结果再更新计数器顺序颠倒会导致错误整数溢出未及时取模导致中间结果溢出尤其在C/Java中负数处理不当如前所述负数取模需要特别处理调试时可以打印每一步的前缀和与计数器状态用小规模数据手工验证对比暴力解法的结果10. 实际应用场景这类算法在实际中有广泛应用金融分析统计满足特定条件的连续交易区间信号处理寻找满足能量特征的信号片段基因组学分析DNA序列中满足碱基组合规律的区段例如在股票分析中可能需要统计连续N天累计涨幅为奇数的时段就可以直接套用这个算法框架。11. 语言特性注意事项在不同编程语言中实现时需注意Python整数不会溢出取模结果总是与数学定义一致但大数运算较慢必要时可用PyPy加速C/Java必须及时取模防止溢出负数取模需要额外处理可以用位运算优化JavaScript数字都是浮点数但位运算会转为32位整数大数需要用BigInt12. 进阶思考与挑战对于想进一步挑战的同学可以尝试空间复杂度能否进一步优化已经O(1)了如果要求同时统计奇数和、偶数和的子数组数量如何修改如果数组可以动态变化增加/删除元素如何维护统计结果线段树应用例如问题2的解法def countSubarrays(arr): prefix 0 cnt [1, 0] # cnt[0] for even, cnt[1] for odd res [0, 0] # res[0] for even, res[1] for odd for num in arr: prefix num mod prefix % 2 res[mod] cnt[0] res[1-mod] cnt[1] cnt[mod] 1 return res # [even_count, odd_count]13. 算法竞赛中的应用技巧在编程竞赛中处理此类问题的经验快速识别问题类型看到连续子数组和要立即想到前缀和模数处理技巧通常题目要求对1e97取模要养成及时取模的习惯测试用例设计自己构造边界用例如全奇数、全偶数、空数组等模板化代码可以准备前缀和的代码模板快速套用14. 学习资源推荐想深入掌握这类算法的同学可以参考《算法导论》第4章 - 分治策略与递归式LeetCode前缀和标签下的经典题目和为K的子数组和可被K整除的子数组和等于k的最长子数组长度竞赛选手的博客如Codeforces上的前缀和技巧分享15. 个人解题心得在解决这个问题时我经历了几个关键突破点最初尝试用滑动窗口但发现窗口性质不满足单调性要求然后想到前缀和但一开始忽略了利用奇偶性质的优化通过具体例子如[1,3,5]手工计算发现了奇偶计数的规律调试时发现初始条件设置错误通过打印中间状态找到问题最大的收获是对于统计类问题寻找不变量或数学规律往往比直接计算更高效。前缀和配合奇偶计数将O(n²)问题降为O(n)这种优化思路值得牢记。
