Medium

题目描述

给你一个二进制数组 nums。

如果一个子数组恰好包含一个值为 1 的元素，那么我们称这个子数组是好的。

请你返回将数组 nums 拆分为若干好子数组的方案数。由于答案可能很大，请将结果对 10^9 + 7 取模后返回。

子数组是数组中一个连续且非空的元素序列。

示例 1：

输入：nums = [0,1,0,0,1]
输出：3
解释：有 3 种方式将 nums 拆分为好子数组：
- [0,1] [0,0,1]
- [0,1,0] [0,1]
- [0,1,0,0] [1]

示例 2：

输入：nums = [0,1,0]
输出：1
解释：有 1 种方式将 nums 拆分为好子数组：
- [0,1,0]

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 1
  • 如果数组只包含 0，答案为 0
  • 在最终拆分中，恰好在两个连续 1 之间存在一个分割点
  • 分割点可以放置的方式有多少种？

解题思路

这道题的关键洞察是：每个好子数组必须恰好包含一个 1。

首先分析特殊情况：

  • 如果数组中没有 1，则无法形成任何好子数组，返回 0
  • 如果数组中只有一个 1，则整个数组就是唯一的好子数组，返回 1

对于一般情况，我们需要理解拆分的本质：

  1. 每个 1 必须被包含在某个好子数组中
  2. 两个相邻的 1 之间必须有一个分割点来分隔它们
  3. 分割点可以放在这两个 1 之间的任何位置

具体算法：

  1. 找到所有 1 的位置
  2. 对于相邻的两个 1，计算它们之间有多少个可能的分割位置
  3. 如果两个 1 的位置分别是 pos1 和 pos2，则分割点可以放在 pos1+1 到 pos2 之间，共有 pos2 - pos1 种选择
  4. 所有相邻 1 对之间的选择数相乘即为总方案数

时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int numberOfGoodSubarraySplits(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        vector<int> ones;
        
        // 找到所有1的位置
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                ones.push_back(i);
            }
        }
        
        // 如果没有1，无法形成好子数组
        if (ones.empty()) return 0;
        
        // 如果只有一个1，只有一种方案
        if (ones.size() == 1) return 1;
        
        long long result = 1;
        // 计算相邻1之间的分割方案数
        for (int i = 0; i < ones.size() - 1; i++) {
            int gap = ones[i + 1] - ones[i];
            result = (result * gap) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numberOfGoodSubarraySplits(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        # 找到所有1的位置
        ones = [i for i, num in enumerate(nums) if num == 1]
        
        # 如果没有1，无法形成好子数组
        if not ones:
            return 0
        
        # 如果只有一个1，只有一种方案
        if len(ones) == 1:
            return 1
        
        result = 1
        # 计算相邻1之间的分割方案数
        for i in range(len(ones) - 1):
            gap = ones[i + 1] - ones[i]
            result = (result * gap) % MOD
        
        return result

public class Solution {
    public int NumberOfGoodSubarraySplits(int[] nums) {
        const int MOD = 1000000007;
        var ones = new List<int>();
        
        // 找到所有1的位置
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 1) {
                ones.Add(i);
            }
        }
        
        // 如果没有1，无法形成好子数组
        if (ones.Count == 0) return 0;
        
        // 如果只有一个1，只有一种方案
        if (ones.Count == 1) return 1;
        
        long result = 1;
        // 计算相邻1之间的分割方案数
        for (int i = 0; i < ones.Count - 1; i++) {
            int gap = ones[i + 1] - ones[i];
            result = (result * gap) % MOD;
        }
        
        return (int)result;
    }
}

var numberOfGoodSubarraySplits = function(nums) {
    const MOD = 1e9 + 7;
    const ones = [];
    
    // 找到所有1的位置
    for (let i = 0; i < nums.length; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次数组找到所有1的位置，然后遍历相邻1对计算方案数
空间复杂度O(k)k为数组中1的个数，最坏情况下为O(n)

相关题目