What is the key pattern used in Ways to Split Array Into Good Subarrays?

The key pattern is state transition dynamic programming, where each dp state depends on distances between consecutive 1s.

How do I handle arrays that contain only zeros?

Return 0 immediately since there are no good subarrays possible if the array has no 1s.

Why do we apply modulo 10^9 + 7 in the solution?

Because the number of ways can be very large, modulo ensures results fit within integer limits.

Can this approach handle arrays up to length 10^5 efficiently?

Yes, identifying 1 positions and using state transition DP ensures an O(n) time solution suitable for large arrays.

What common mistake occurs in computing dp states?

A common mistake is miscounting the number of zeros between 1s or forgetting to multiply correctly for multiple partition options.

#2750

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

将数组划分成若干好子数组的方式

给你一个二元数组 nums 。如果数组中的某个子数组恰好只存在一个值为 1 的元素，则认为该子数组是一个好子数组。请你统计将数组 nums 划分成若干好子数组的方法数，并以整数形式返回。由于数字可能很大，返回其对 10 9 + 7 取余之后的结果。子数组是数组中的一个连续非…

数组数学动态规划

题目描述

给你一个二元数组 nums 。

如果数组中的某个子数组恰好只存在一个值为 1 的元素，则认为该子数组是一个 好子数组 。

请你统计将数组 nums 划分成若干 好子数组 的方法数，并以整数形式返回。由于数字可能很大，返回其对 10⁹ + 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⁵
0 <= nums[i] <= 1

lightbulb

解题思路

方法一：乘法原理

根据题目描述，我们可以在两个 $1$ 之间画一条分割线，假设两个 $1$ 之间的下标分别为 $j$ 和 $i$ ，那么可以画的不同分割线的数量为 $i - j$ 。我们找出所有满足条件的 $j$ 和 $i$ ，然后将所有的 $i - j$ 相乘即可。如果找不到两个 $1$ 之间的分割线，那么说明数组中不存在 $1$ ，此时答案为 $0$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numberOfGoodSubarraySplits(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        ans, j = 1, -1
        for i, x in enumerate(nums):
            if x == 0:
                continue
            if j > -1:
                ans = ans * (i - j) % mod
            j = i
        return 0 if j == -1 else ans

speed

复杂度分析

指标	值
时间	complexity is O(n) for a single pass to identify 1 positions and compute dp transitions. Space complexity is O(k) where k is the number of 1s, as we only store dp states and positions of 1s.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check for edge case when the array contains only zeros; answer should be 0.
question_mark
Ask about handling large arrays and modulo operations to prevent integer overflow.
question_mark
Probe understanding of state transition DP and distances between consecutive 1s.

warning

常见陷阱

外企场景

error
Forgetting to return 0 when there are no 1s in the array.
error
Incorrectly handling zeros at the beginning or end of the array in the DP calculation.
error
Neglecting the modulo operation, which can cause integer overflow for large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow subarrays to contain at most one 1 instead of exactly one 1, changing the DP transition rules.
arrow_right_alt
Count splits where each good subarray contains exactly k ones, requiring generalized state transitions.
arrow_right_alt
Consider arrays with more than two distinct values, extending the definition of good subarrays.

help

常见问题

外企场景

继续练习

#2681 英雄的力量 #2597 美丽子集的数目 #2572 无平方子集计数