What is a good partition in Count the Number of Good Partitions?

A good partition divides the array into contiguous subarrays such that no number appears in more than one subarray, with each subarray containing all occurrences of its numbers.

Why use hash maps for this problem?

Hash maps store the last index of each number, ensuring segments include all occurrences without repetition, which is the core pattern for this array scanning problem.

Can duplicates appear within a single subarray?

Yes, duplicates can appear inside one subarray, but they cannot be split across multiple subarrays in a good partition.

What is the expected time complexity?

Scanning the array with hash lookups and dynamic programming yields roughly O(n) time complexity, efficient even for the maximum length of 105.

How do I handle very large values in nums?

Values themselves are only used as hash keys, so large numbers up to 109 do not impact the algorithm's correctness or efficiency.

#2963

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计好分割方案的数目

给你一个下标从 0 开始、由正整数组成的数组 nums 。将数组分割成一个或多个连续子数组，如果不存在包含了相同数字的两个子数组，则认为是一种好分割方案。返回 nums 的好分割方案的数目。由于答案可能很大，请返回答案对 10 9 + 7 取余的结果。示例 1：输入：…

数组哈希表数学组合数学

题目描述

给你一个下标从 0 开始、由 正整数 组成的数组 nums。

将数组分割成一个或多个连续子数组，如果不存在包含了相同数字的两个子数组，则认为是一种 好分割方案 。

返回 nums 的 好分割方案 的数目。

由于答案可能很大，请返回答案对 10⁹ + 7 取余的结果。

示例 1：

输入：nums = [1,2,3,4]
输出：8
解释：有 8 种 好分割方案 ：([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]) 和 ([1,2,3,4]) 。

示例 2：

输入：nums = [1,1,1,1]
输出：1
解释：唯一的 好分割方案 是：([1,1,1,1]) 。

示例 3：

输入：nums = [1,2,1,3]
输出：2
解释：有 2 种 好分割方案 ：([1,2,1], [3]) 和 ([1,2,1,3]) 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：哈希表 + 分组 + 快速幂

根据题目描述，我们可以知道，相同的数字必须在同一个子数组中。因此，我们用一个哈希表 $last$ 记录每个数字最后一次出现的下标。

接下来，我们用一个下标 $j$ 标识已经出现过的元素中最后一个元素的下标，用一个变量 $k$ 记录当前可以划分的子数组的个数。

然后，我们从左到右遍历数组 $nums$ ，对于当前遍历到的数字 $nums[i]$ ，我们获取其最后一次出现的下标，更新 $j = \max(j, last[nums[i]])$ 。如果 $i = j$ ，那么说明当前位置可以是一个子数组的结尾，我们将 $k$ 增加 $1$ 。继续遍历，直到遍历完整个数组。

最后，我们考虑 $k$ 个子数组的划分方案数。子数组数量为 $k$ ，有 $k-1$ 个位置可以划分（拼接），因此方案数为 $2^{k-1}$ 。由于答案可能很大，我们需要对 $10^9 + 7$ 取模。这里我们可以使用快速幂来加速运算。

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

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        last = {x: i for i, x in enumerate(nums)}
        mod = 10**9 + 7
        j, k = -1, 0
        for i, x in enumerate(nums):
            j = max(j, last[x])
            k += i == j
        return pow(2, k - 1, mod)

speed

复杂度分析

指标	值
时间	complexity depends on scanning the array and updating hash maps, approximately O(n). Space complexity is O(n) for storing last occurrences and dynamic counts, scalable to 105 elements.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate checks last positions of numbers to avoid overlaps in subarrays.
question_mark
Candidate uses dynamic programming or combinatorics to count partitions.
question_mark
Candidate explains why extending a segment beyond a repeated number would invalidate the partition.

warning

常见陷阱

外企场景

error
Failing to include all occurrences of a number in the same subarray, causing invalid partitions.
error
Overcounting partitions by ignoring previous segment boundaries.
error
Inefficient hash map lookups or unnecessary nested loops leading to timeouts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count good partitions with at most k subarrays.
arrow_right_alt
Return the number of partitions where each subarray has unique sums.
arrow_right_alt
Partition arrays into subarrays avoiding duplicate numbers within any segment.

help

常见问题

外企场景

继续练习

#3128 直角三角形 #3312 查询排序后的最大公约数 #2597 美丽子集的数目