其乘积为偶数的子数组的数量？

Question

给定一个大小为 n 的数组，n<=10^5 计算乘积为偶数的子数组数量的有效方法是什么？ 我正在使用 (On^3) 时间复杂度的天真方法？ 请提出一些有效的方法？

Answer 1

注意：根据你的解释，我的印象是你正在获取所有子数组，计算乘积并检查它是否偶数。

但是有一个非常重要的数学规则：当你有一系列自然数时，只要有一个偶数，乘积就是偶数。

所以，我建议您编写以下算法：

1. 在数组中搜索偶数。
2. 计算包含该偶数的子数组的数量。
3. 在数组中搜索下一个偶数。
4. 计算子数组的数量，包含下一个偶数，但不包含前一个偶数。
5. 继续，直到处理完数组中的所有偶数。