Question

2963. 统计好分割方案的数目

English Version

题目描述

给你一个下标从 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

解法

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

根据题目描述，我们可以知道，相同的数字必须在同一个子数组中。因此，我们用一个哈希表 $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$ 的长度。

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)

class Solution {
  public int numberOfGoodPartitions(int[] nums) {
    Map<Integer, Integer> last = new HashMap<>();
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      last.put(nums[i], i);
    }
    final int mod = (int) 1e9 + 7;
    int j = -1;
    int k = 0;
    for (int i = 0; i < n; ++i) {
      j = Math.max(j, last.get(nums[i]));
      k += i == j ? 1 : 0;
    }
    return qpow(2, k - 1, mod);
  }

  private int qpow(long a, int n, int mod) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return (int) ans;
  }
}

class Solution {
public:
  int numberOfGoodPartitions(vector<int>& nums) {
    unordered_map<int, int> last;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      last[nums[i]] = i;
    }
    const int mod = 1e9 + 7;
    int j = -1, k = 0;
    for (int i = 0; i < n; ++i) {
      j = max(j, last[nums[i]]);
      k += i == j;
    }
    auto qpow = [&](long long a, int n, int mod) {
      long long ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return (int) ans;
    };
    return qpow(2, k - 1, mod);
  }
};

func numberOfGoodPartitions(nums []int) int {
  qpow := func(a, n, mod int) int {
    ans := 1
    for ; n > 0; n >>= 1 {
      if n&1 == 1 {
        ans = ans * a % mod
      }
      a = a * a % mod
    }
    return ans
  }
  last := map[int]int{}
  for i, x := range nums {
    last[x] = i
  }
  const mod int = 1e9 + 7
  j, k := -1, 0
  for i, x := range nums {
    j = max(j, last[x])
    if i == j {
      k++
    }
  }
  return qpow(2, k-1, mod)
}

function numberOfGoodPartitions(nums: number[]): number {
  const qpow = (a: number, n: number, mod: number) => {
    let ans = 1;
    for (; n; n >>= 1) {
      if (n & 1) {
        ans = Number((BigInt(ans) * BigInt(a)) % BigInt(mod));
      }
      a = Number((BigInt(a) * BigInt(a)) % BigInt(mod));
    }
    return ans;
  };
  const last: Map<number, number> = new Map();
  const n = nums.length;
  for (let i = 0; i < n; ++i) {
    last.set(nums[i], i);
  }
  const mod = 1e9 + 7;
  let [j, k] = [-1, 0];
  for (let i = 0; i < n; ++i) {
    j = Math.max(j, last.get(nums[i])!);
    if (i === j) {
      ++k;
    }
  }
  return qpow(2, k - 1, mod);
}