分割数组为连续子序列如何用贪心判断？为什么优先延长已有序列？

简化版

分割数组为连续子序列的贪心原则是：遇到数字 x 时，优先把它接到一个以 x-1 结尾的已有子序列后面；如果接不上，再尝试新开 x,x+1,x+2 长度至少为 3 的序列。两者都不行就返回 false。

详细版

用 count 记录每个数字剩余次数，用 need 记录有多少条子序列正等待某个数字。遍历数组中的 x，若 count[x]==0 跳过；若 need[x]>0，说明有序列等着 x，优先接上并让它接下来等待 x+1；否则检查 x+1 和 x+2 是否还有剩余，能的话新开一条长度 3 的序列。

优先延长已有序列是为了避免短序列无法达到长度 3。时间复杂度 O(n)，空间复杂度 O(n)。

完整版教学

一、题目为什么卡在“长度至少为 3”

如果只是分成连续子序列，没有长度限制会很简单；难点在于每条子序列长度至少为 3。短序列如果后续接不到数字，就会失败。

nums = [1,2,3,3,4,5]
可以分成 [1,2,3] 和 [3,4,5]

处理第二个 3 时，如果随便新开或延长，都会影响后续 4,5 的归属。

二、为什么优先延长已有序列

假设有一条序列已经在等 x，如果你不把 x 给它，而是拿 x 去新开序列，那么旧序列可能永远无法合法结束。已有序列通常已经消耗了前面的数字，放弃它的成本更高。

当前数字 x 的选择	风险
延长等待 x 的旧序列	旧序列继续合法
新开 x,x+1,x+2	旧序列可能断掉

记忆钩子：连续子序列先救“已经开工的坑”，再考虑新开项目。

这就是 need 哈希表的作用：记录谁正在等当前数字。

三、两个哈希表分别表示什么

count[x] 表示数字 x 还有多少个没使用。need[x] 表示有多少条已有子序列下一步需要 x。

count：库存
need：订单

处理 x 时：

如果库存 count[x] 为 0：跳过
如果订单 need[x] > 0：优先满足订单
否则：尝试用 x,x+1,x+2 新开序列

这个“库存 + 订单”的比喻很适合面试解释。

四、为什么新开必须一次拿到 x+1 和 x+2

题目要求每条序列长度至少为 3。新开一条以 x 开头的序列，如果拿不到 x+1 和 x+2，这条序列从出生开始就不可能合法。

新开：[x, x+1, x+2]
之后它需要：x+3

所以新开时要立即扣掉三个数字的库存，并把 need[x+3]++。不能只开 [x] 或 [x,x+1] 这种半成品。

五、代码模板

boolean isPossible(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    Map<Integer, Integer> need = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
    for (int x : nums) {
        if (count.getOrDefault(x, 0) == 0) continue;
        if (need.getOrDefault(x, 0) > 0) {
            count.put(x, count.get(x) - 1);
            need.put(x, need.get(x) - 1);
            need.put(x + 1, need.getOrDefault(x + 1, 0) + 1);
        } else if (count.getOrDefault(x + 1, 0) > 0 && count.getOrDefault(x + 2, 0) > 0) {
            count.put(x, count.get(x) - 1);
            count.put(x + 1, count.get(x + 1) - 1);
            count.put(x + 2, count.get(x + 2) - 1);
            need.put(x + 3, need.getOrDefault(x + 3, 0) + 1);
        } else {
            return false;
        }
    }
    return true;
}

输入数组已按非递减顺序，这是题目常见前提。若没有排序，需要先排序。

六、用例子推演

nums=[1,2,3,3,4,5]：

1：没有旧序列等 1，新开 [1,2,3]，need[4]++
第二个 3：没有旧序列等 3，新开 [3,4,5]，need[6]++

如果处理 4 时发现 need[4]>0，就优先接到 [1,2,3] 后面，而不是拿它去新开别的序列。

这种优先级能最大限度避免已经形成的短序列断掉。

七、常见误区与追问

误区：先新开序列再延长旧序列。 可能让旧序列缺少等待的数字而失败。
误区：新开时只拿 x 和 x+1。 长度至少为 3，必须同时保证 x+2 存在。
误区：忘记减少 count。 数字被使用后必须从库存中扣掉。
追问：need 表示什么？ 表示已有子序列下一步需要某个数字的数量。
追问：为什么遍历顺序重要？ 从小到大处理能保证子序列按连续递增方向构造。
追问：复杂度是多少？ 每个数字处理常数次，时间 O(n)，空间 O(n)。

八、加强记忆

这题记成“库存 count + 订单 need”。数字 x 来了，先看有没有序列等它；有就优先延长，因为旧坑不填可能烂尾。没有旧坑时，才检查 x,x+1,x+2 能不能新开一条合格序列。优先延长、谨慎新开，是这题的贪心魂。

简化版

详细版