c++ - 乘积为偶数的子数组的数量？

Question

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

标签： c++arrayssub-array

Answer 1

请注意：从您的解释中，我的印象是您正在获取所有子数组，计算产品并检查它是否是偶数。

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

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

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