全 0 子数组的数目
难度:
标签:
题目描述
代码结果
运行时间: 75 ms, 内存: 26.6 MB
/*
题目思路:
1. 使用 Java Stream 和数组流对数组进行操作。
2. 将所有元素转为 0 或 1,0 表示原数组的零,1 表示原数组的非零。
3. 找出所有的全零子数组长度,计算全零子数组的数量。
*/
import java.util.stream.IntStream;
public class Solution {
public int countZeroSubarrays(int[] nums) {
int[] zeros = IntStream.of(nums).map(num -> num == 0 ? 0 : 1).toArray();
int count = 0;
int zeroLength = 0;
for (int zero : zeros) {
if (zero == 0) {
zeroLength++;
count += zeroLength;
} else {
zeroLength = 0;
}
}
return count;
}
}
解释
方法:
此题解采用一遍扫描的方式计算所有全0子数组的数目。使用变量res来存储子数组的总数,变量nZeros来记录连续0的长度。遍历数组nums,每遇到一个0,nZeros增加1。遇到非0数字时,如果nZeros大于0,说明之前有一段连续的0,根据连续0的数量计算可以形成的子数组数目并加到res上,然后重置nZeros为0。遍历结束后,如果数组的最后一部分是连续的0,需要再处理一次这部分数据。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在`res += (1+nZeros)*nZeros//2`这一步中,为什么采用这种公式来计算子数组的数量?这个公式的数学原理是什么?
▷🦆
代码中对于最后一段连续的0是如何处理的?为什么需要在循环结束后单独处理?
▷🦆
如果输入数组中没有0,代码的行为是怎样的?这种情况下是否还有必要进行任何计算?
▷🦆
代码在处理连续0时,是否考虑了可能的整数溢出问题,尤其是当数组非常大且全为0时?
▷