leetcode
leetcode 2001 ~ 2050
全 0 子数组的数目

全 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`这一步中,为什么采用这种公式来计算子数组的数量?这个公式的数学原理是什么?
这个公式的数学原理基于组合数学中的连续自然数求和公式。假设有n个连续的0,可以形成的全0子数组是:单个0为1个子数组,连续两个0为1个子数组,以此类推,直到连续n个0为1个子数组。这是一个等差数列求和的问题,其中第1项是1,最后1项是n,项数也是n。等差数列求和公式为`(首项 + 末项) * 项数 / 2`,这里即为`(1+n)*n/2`。这个公式直接计算了从1到n的所有可能的连续子数组数目的总和。
🦆
代码中对于最后一段连续的0是如何处理的?为什么需要在循环结束后单独处理?
代码中单独处理最后一段连续的0是因为在遍历数组时,只有遇到非0元素后才会计算前面连续0形成的子数组。如果数组最后一部分是连续的0,遍历结束时不会再遇到非0元素触发计算,因此需要在循环结束后,单独对nZeros进行一次检查,如果nZeros大于0,则再进行一次子数组数量的计算,确保这部分也被正确统计。
🦆
如果输入数组中没有0,代码的行为是怎样的?这种情况下是否还有必要进行任何计算?
如果输入数组中没有0,那么变量nZeros将始终为0,因此每次遇到非0元素时,由于nZeros为0,计算子数组的分支不会执行。同样,循环结束后的额外处理也不会执行,因为nZeros仍为0。在这种情况下,res初始化为0,且在执行过程中不会有任何增加,最终返回的也是0。这种情况下没有必要进行0子数组的计算,代码自然地处理了这种情况,效率很高。
🦆
代码在处理连续0时,是否考虑了可能的整数溢出问题,尤其是当数组非常大且全为0时?
原始代码并没有显式地处理整数溢出问题。Python的整数类型在内部使用变长表示,理论上只受限于机器的内存,不会像固定位宽的整数类型那样容易溢出。然而,在实际应用中,如果数组非常大,计算`(1+nZeros)*nZeros//2`可能导致内存使用过大。在实际部署中可能需要考虑此类极端情况,通过适当的算法优化或事先检查数组大小来处理可能的资源耗尽问题。

相关问题