题目描述
给你一个二元数组 nums
。
如果数组中的某个子数组 恰好 只存在 一 个值为 1
的元素,则认为该子数组是一个 好子数组。
请你统计将数组 nums
划分成若干 好子数组 的方法数,并以整数形式返回。由于数字可能很大,返回其对 10^9 + 7
取余 之后的结果。
子数组是数组中的一个连续 非空 元素序列。
样例
输入:nums = [0,1,0,0,1]
输出:3
解释:存在 3 种可以将 nums 划分成若干好子数组的方式:
- [0,1] [0,0,1]
- [0,1,0] [0,1]
- [0,1,0,0] [1]
输入:nums = [0,1,0]
输出:1
解释:存在 1 种可以将 nums 划分成若干好子数组的方式:
- [0,1,0]
限制
1 <= nums.length <= 10^5
0 <= nums[i] <= 1
算法
(数学) $O(n)$
- 考虑在相邻的两个 $1$ 的位置中间放置隔板进行划分。根据乘法原理,每个相邻的位置的隔板方案数的乘积就是答案
时间复杂度
- 遍历数组一次,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
int numberOfGoodSubarraySplits(vector<int>& nums) {
const int n = nums.size();
const int mod = 1000000007;
int ans = 1, prev = -1;
for (int i = 0; i < n; i++) {
if (nums[i] != 1)
continue;
if (prev != -1)
ans = (LL)(ans) * (i - prev) % mod;
prev = i;
}
if (prev == -1)
return 0;
return ans;
}
};