统计好分割方案的数目

标签: 数组 哈希表 数学 组合数学

难度: Hard

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

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

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

由于答案可能很大，请返回答案对 109 + 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 <= 105
  • 1 <= nums[i] <= 109

Submission

运行时间: 131 ms

内存: 35.4 MB

MOD = 10 ** 9 + 7
class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        # 同一个数字必须分在一个组里
        # 且要连续
        # 记录每个数字最右边出现的下标
        dic = {}
        for i, x in enumerate(nums):
            dic[x] = i
        n = len(nums)
        # ll存储了除0外，所有子数组至少开始的左端点
        m = max_r = 0
        for i, x in enumerate(nums):
            max_r = dic[x] if dic[x] > max_r else max_r
            if max_r == i:
                m += 1
        ans = pow(2, m - 1, MOD)
        return ans

Explain

题解的核心思路是识别数组中可以形成好分割的点。首先，创建一个字典来记录每个元素最后一次出现的位置。然后遍历数组，对每个元素更新其最后一次出现的位置，同时维护一个变量max_r来记录当前遍历到的位置所能达到的最远右边界。当遍历的索引与max_r相等时，意味着到目前为止的所有元素可以构成一个好分割的子数组。每识别出一个这样的点，我们将计数器加一。最终，好分割的方案数为2的(m-1)次方，其中m是识别出的好分割点的数量，因为每一个好分割点都可以选择分割或不分割。

时间复杂度: O(n)

空间复杂度: O(n)

MOD = 10 ** 9 + 7

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        # 创建字典记录每个数字最后一次出现的索引
        dic = {}
        for i, x in enumerate(nums):
            dic[x] = i
        n = len(nums)
        # 初始化分割计数器和当前的最大右边界
        m = max_r = 0
        for i, x in enumerate(nums):
            max_r = max(max_r, dic[x])  # 更新最大右边界
            if max_r == i:
                m += 1  # 如果当前索引等于最大右边界，增加分割计数器
        # 分割方案数为2的(m-1)次方
        ans = pow(2, m - 1, MOD)
        return ans

Explore

在这个问题中，记录每个元素最后一次出现的位置是为了确定一个元素在数组中的'影响范围'，即如果要形成一个不包含重复元素的子数组，该元素最远可以到达的位置。如果记录所有出现的位置，虽然信息更全面，但实际上并不需要这么多细节来解决问题。只需要知道每个元素最远能延伸到哪里，就可以决定在何处可以安全地进行分割，从而形成不包含重复元素的子数组。

选择`max(max_r, dic[x])`是为了确保当前考虑的子数组包含了目前元素`x`的所有出现。这种方法通过不断更新此右边界，确保了当前子数组的界限至少要包括当前元素的最后出现位置。这样的处理确保了所有元素只属于一个子数组内，并且每个子数组是最小的、不包含重复元素的子数组。

当遍历索引`i`与最大右边界`max_r`相等时，意味着从上一个分割点（或数组开始）到当前位置`i`的范围内，没有任何一个元素的最后出现位置超过`i`。这表明这个区间内的所有元素都只出现在这个区间内，没有跨区间重复。因此，这个子数组是不包含重复元素的，可以形成一个好分割。

题解中的逻辑是基于识别出的`m`个好分割点，每个分割点都可以选择分割或不分割，从而形成不同的子数组组合。但是，最后一个分割点实际上是数组的末尾，它之后没有更多的元素可以形成新的子数组，因此它不需要作为一个选择点。所以，实际的选择点是`m-1`个。因此，总的分割方案数是`2的(m-1)次方`。