难度: Medium
Submission
运行时间: 67 ms
内存: 27.1 MB
class Solution:
def evenProduct(self, nums: List[int]) -> int:
n = len(nums)
nums.append(0)
ans = dp = 0
for x in nums:
if x & 1:
dp += 1
else:
ans -= dp * (dp + 1)
dp = 0
return (n * (n + 1) + ans) // 2
Explain
本题解采用动态规划思想，通过统计子数组内奇数的数量来确定子数组乘积的奇偶性。首先，对于数组中的每个元素，如果它是奇数，计数器 dp 自增；如果是偶数，则计算以当前偶数结束的子数组中奇数的数量，并更新累计答案 ans。最后，通过总子数组数量减去含有奇数乘积的子数组数量来得到乘积为偶数的子数组数量。
时间复杂度: O(n)
空间复杂度: O(1)
# 定义类和方法
class Solution:
def evenProduct(self, nums: List[int]) -> int:
n = len(nums) # 数组长度
nums.append(0) # 添加一个偶数以处理尾部
ans = dp = 0 # 初始化结果和当前奇数计数
for x in nums:
if x & 1: # 如果x是奇数
dp += 1 # 增加奇数计数器
else: # x是偶数
ans -= dp * (dp + 1) # 计算以x结尾的子数组中奇数乘积的子数组数量
dp = 0 # 重置奇数计数器
return (n * (n + 1) + ans) // 2 # 计算总的偶数乘积子数组数
Explore
在数组末尾添加一个额外的偶数元素是为了确保最后一个可能的奇数子数组被正确地处理和统计。因为算法中的逻辑是在遇到偶数时，计算以该偶数结束的子数组中包含奇数乘积的子数组数量，并重置奇数计数器。如果数组的最后一个元素是奇数，不添加偶数元素的话，这些奇数会形成的子数组将不会被考虑在最终的统计中。因此，添加一个偶数可以触发对这部分子数组的处理，确保所有可能的子数组都被正确计算。
这个公式用于计算以偶数结尾并且包含奇数乘积的子数组的数量。公式 `dp * (dp + 1)` 是基于组合计数原理推导的。其中 `dp` 表示到当前位置为止奇数的总数，`dp * (dp + 1) / 2` 表示所有可能的以奇数结尾的连续子数组数量。由于我们计算的是以偶数结束的子数组数量，整个公式 `dp * (dp + 1)` 实际上计算的是这些以奇数结尾的子数组与当前偶数形成新的以偶数结尾的子数组的数量。由于算法的目标是统计奇数乘积的子数组，所以这个公式会从总数中减去，以得到乘积为偶数的子数组数量。
算法中，在遇到偶数并处理完所有相关子数组后重置奇数计数器 `dp` 是因为我们只关心以当前位置结尾的子数组。之前的奇数计数已经在遇到每个偶数时被充分利用，计算了所有以那些偶数结尾的子数组数量。重置 `dp` 是为了重新开始计数新一段的奇数，之前的计数已经不再需要，因为它们对于后续的子数组计算已无影响。
通过在数组末尾添加一个额外的偶数元素，我们确保了即使数组的最后一个元素是奇数，所有以它为结束点的子数组也会被计算。这样做的原因是因为算法在遇到偶数时会计算以此为结尾的、包含奇数乘积的子数组数量，并进行重置，从而处理所有之前的连续奇数。添加的偶数确保这一逻辑也适用于原数组的最后一个元素（如果它是奇数的话）。这种方法保证了所有子数组被遍历并正确计算，无论它们的结束元素是奇数还是偶数。