DeepSeek LeetCode 2963. 统计好分割方案的数目 Java实现

好的这道题我们先理解一下题意然后再给出 Java 实现。题目理解LeetCode 2963. 统计好分割方案的数目好分割的定义将数组分割成若干个连续的非空子数组使得每个数字在所有的子数组中最多出现一次。换句话说对于一个数字它在原数组中出现的所有位置必须属于同一个子数组不能跨两个不同的子数组。---思路1. 记录每个数字的最后出现位置· 遍历一次数组用 lastPos[x] 记录数字 x 最后一次出现的下标。2. 贪心扫描划分点· 从左到右遍历数组维护当前段需要覆盖到的最大右边界 currEnd。· 当遍历到下标 i更新 currEnd max(currEnd, lastPos[nums[i]])。· 如果 i currEnd说明当前位置可以作为一个分割点这个段的最后一个位置。· 每找到一个分割点可能的分段方式就会翻倍因为可以在这些分割点处选择切或不切。3. 计算方案数· 如果有 k 个可分割的位置不包括数组末尾那么方案数为 2^(k)。· 注意整个数组必须作为一个完整的分割所以 k 指的是中间可切开的位置数。· 用快速幂或逐次乘 2 来避免溢出。---举例示例nums [1, 1, 2, 2, 3, 3]· lastPos:1 → 12 → 33 → 5遍历· i0, currEnd lastPos[1] 1 → i ! currEnd· i1, currEnd max(1, lastPos[1]1) 1, i currEnd → 切分点 1· i2, currEnd max(1, lastPos[2]3) 3· i3, currEnd max(3, lastPos[2]3) 3, i currEnd → 切分点 1· i4, currEnd max(3, lastPos[3]5) 5· i5, currEnd max(5, lastPos[3]5) 5, i currEnd → 切分点 1切分点位置1, 3, 53个分段数 2^3 8---Java 实现javaclass Solution {public int numberOfGoodPartitions(int[] nums) {MapInteger, Integer lastPos new HashMap();int n nums.length;// 记录每个数字最后出现的位置for (int i 0; i n; i) {lastPos.put(nums[i], i);}int segments 0;int currEnd 0;for (int i 0; i n; i) {currEnd Math.max(currEnd, lastPos.get(nums[i]));if (i currEnd) {segments;}}// 有 segments 段中间有 segments-1 个切割点每个切割点可以切或不切// 所以总方案数 2^(segments-1)long ans 1;int MOD 1_000_000_007;for (int i 1; i segments; i) {ans (ans * 2) % MOD;}return (int) ans;}}---复杂度分析· 时间复杂度O(n)· 空间复杂度O(n)存储每个数字最后出现的位置---总结核心是找到所有必须合并在一起形成的“块”块的数量决定了中间有多少个可选的切割点每个切割点独立决定切或不切因此方案数为 2^(块数-1)。