Hard

题目描述

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

将数组分割成一个或多个 连续 子数组的分割方案是 好的 ，当且仅当没有两个子数组包含相同的数字。

返回 nums 中好分割方案的 总数 。

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

解题思路

这道题的核心思想是理解"好分割"的约束条件：如果一个子数组包含某个数字，那么它必须包含这个数字的所有出现位置。

解题思路

首先，我们需要找出每个数字的最后出现位置。对于任何包含数字 x 的子数组，它的结束位置至少要延伸到 x 的最后出现位置。

接下来，我们可以使用贪心策略找到所有必须的分割段：

  1. 维护当前段必须延伸到的最远位置 maxEnd
  2. 从左到右扫描数组，对于每个位置的数字，更新 maxEnd 为该数字最后出现位置
  3. 当到达 maxEnd 时，说明找到了一个完整的段

找到所有必须的段后，问题转化为：如何将这些段进行分组？如果有 m 个必须的段，我们可以在相邻段之间选择是否插入分割点，共有 m-1 个可选分割点，因此总方案数为 2^(m-1)。

算法步骤

  1. 记录每个数字的最后出现位置
  2. 使用贪心策略找出所有必须的段
  3. 计算 2^(段数-1) 作为答案

代码实现

class Solution {
public:
    int numberOfGoodPartitions(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        
        // 记录每个数字的最后出现位置
        unordered_map<int, int> lastPos;
        for (int i = 0; i < n; i++) {
            lastPos[nums[i]] = i;
        }
        
        // 找出所有必须的段
        int segments = 0;
        int maxEnd = -1;
        
        for (int i = 0; i < n; i++) {
            maxEnd = max(maxEnd, lastPos[nums[i]]);
            if (i == maxEnd) {
                segments++;
            }
        }
        
        // 计算 2^(segments-1)
        long long result = 1;
        for (int i = 0; i < segments - 1; i++) {
            result = (result * 2) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # 记录每个数字的最后出现位置
        last_pos = {}
        for i in range(n):
            last_pos[nums[i]] = i
        
        # 找出所有必须的段
        segments = 0
        max_end = -1
        
        for i in range(n):
            max_end = max(max_end, last_pos[nums[i]])
            if i == max_end:
                segments += 1
        
        # 计算 2^(segments-1)
        return pow(2, segments - 1, MOD)

public class Solution {
    public int NumberOfGoodPartitions(int[] nums) {
        const int MOD = 1000000007;
        int n = nums.Length;
        
        // 记录每个数字的最后出现位置
        Dictionary<int, int> lastPos = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            lastPos[nums[i]] = i;
        }
        
        // 找出所有必须的段
        int segments = 0;
        int maxEnd = -1;
        
        for (int i = 0; i < n; i++) {
            maxEnd = Math.Max(maxEnd, lastPos[nums[i]]);
            if (i == maxEnd) {
                segments++;
            }
        }
        
        // 计算 2^(segments-1)
        long result = 1;
        for (int i = 0; i < segments - 1; i++) {
            result = (result * 2) % MOD;
        }
        
        return (int)result;
    }
}

var numberOfGoodPartitions = function(nums) {
    const MOD = 1000000007;
    const n = nums.length;
    
    // Find the last occurrence of each number
    const lastOccurrence = new Map();
    for (let i = 0; i < n; i++) {
        lastOccurrence.set(nums[i], i);
    }
    
    let partitions = 0;
    let maxEnd = -1;
    
    for (let i = 0; i < n; i++) {
        maxEnd = Math.max(maxEnd, lastOccurrence.get(nums[i]));
        
        // If we've reached the end of current partition
        if (i === maxEnd) {
            partitions++;
        }
    }
    
    // Number of good partitions is 2^(partitions-1)
    if (partitions === 0) return 1;
    
    let result = 1;
    for (let i = 0; i < partitions - 1; i++) {
        result = (result * 2) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(k)

其中 n 是数组长度，k 是不同数字的个数。

相关题目