乘积为偶数的子数组数
难度:
标签:
题目描述
代码结果
运行时间: 67 ms, 内存: 27.1 MB
/*
* 思路:
* 1. 使用Java Stream API, 遍历数组, 生成所有子数组。
* 2. 对每个子数组, 计算其乘积, 如果乘积是偶数, 则计数器加一。
* 3. 返回计数器的值。
*/
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Solution {
public long countEvenProductSubarrays(int[] nums) {
return IntStream.range(0, nums.length)
.boxed()
.flatMap(i -> IntStream.range(i, nums.length)
.mapToObj(j -> IntStream.rangeClosed(i, j).map(k -> nums[k]).toArray()))
.mapToLong(subarray -> {
int product = 1;
for (int num : subarray) {
product *= num;
}
return product % 2 == 0 ? 1 : 0;
})
.sum();
}
}
解释
方法:
本题解采用动态规划思想,通过统计子数组内奇数的数量来确定子数组乘积的奇偶性。首先,对于数组中的每个元素,如果它是奇数,计数器 dp 自增;如果是偶数,则计算以当前偶数结束的子数组中奇数的数量,并更新累计答案 ans。最后,通过总子数组数量减去含有奇数乘积的子数组数量来得到乘积为偶数的子数组数量。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在处理数组时要在末尾添加一个额外的偶数元素,这对算法的逻辑有什么具体影响?
▷🦆
在计算以x结尾的子数组中奇数乘积的子数组数量时,为什么使用`ans -= dp * (dp + 1)`这个公式?这个公式是如何推导出来的?
▷🦆
在重置奇数计数器dp后,为什么不需要对之前的奇数计数进行任何其他操作或保存?
▷🦆
如何确保在算法中遍历结束时,所有的子数组都已经被正确地计算了?特别是在遇到最后一个元素为奇数时。
▷