LeetCode 659. 分割数组为连续子序列

2022-04-28 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 659. 分割数组为连续子序列

题意分析

要什么：给一个已按非递减排好序的整数数组，判断能否把它的全部元素划分成若干组，每组都是「连续递增（相邻差 1）且长度至少为 3」的序列。返回布尔值。
约束透露的信号：输入已经有序，这消除了排序开销，也让我们可以按数值从小到大依次处理，保证「处理到 x 时，所有小于 x 的元素都已经被安置好」。题目只问可行性、不要求输出方案，说明不必记录每条序列具体由哪些元素组成，只需记住「有多少条序列正等着某个数值来接续」。元素规模到 $10^4$ 以上，需要线性或近线性做法，暴力枚举分组方式不可行。
边界：必须用完所有元素，不能丢弃任何一个；长度只有下界 3 而没有上界，所以序列可以任意长；相同数值可以出现多次，它们必须分属不同的序列（同一序列中数值严格递增）；数组长度小于 3 时必然失败。

解法：哈希计数 + 贪心接龙

核心思路

暴力是搜索：对每个元素尝试「接到某条已有序列」或「另起一条新序列」，回溯所有组合，指数级不可行。
瓶颈在于状态爆炸，但仔细看会发现：一条已经建好的序列，对未来唯一有用的信息只有它的结尾数值——结尾是 x 的序列，接下来只可能接 x+1。至于它有多长、由哪些数组成，只要长度已经达标就与后续无关。这把「记录所有序列」压缩成「记录每个数值上挂着多少条待续序列」。
接着是贪心策略的选择。处理数值 x 时有两个选项：接到某条以 x-1 结尾的序列后面，或者新开一条 x, x+1, x+2。应当优先接续。理由是交换论证：假设某个最优方案里 x 被用来新开序列，而同时存在一条以 x-1 结尾的待续序列 S。把 x 改为接到 S 上，再把原新序列的其余成员（x+1, x+2, ...）……更直接的说法是：接续不会让任何序列变短（S 只会更长，且已达标的序列继续变长永远合法），而新开序列会引入一条长度仅 3 的「脆弱」序列，额外消耗掉本可用于接续的 x+1 和 x+2。因此优先接续是安全的。
由此确定要维护的两张表与不变量：freq[v] = 数值 v 还有多少个尚未被使用；need[v] = 已经建成的序列中，有多少条正好以 v-1 结尾、等着一个 v 来接续。处理完前缀中所有小于等于 x 的元素后，这两张表准确描述了剩余资源与未完成的接续承诺。注意 need 里的每一条承诺对应的序列长度都已经至少为 3，这是关键——新开序列时我们一次性消耗三个元素并把承诺记在 x+3 上，所以任何进入 need 的序列天然已经达标，永远不会出现「长度不够却被迫结束」的情况。

解题步骤

先遍历一遍统计 freq。为什么要先统计：新开序列时需要知道 x+1、x+2 是否还有剩余，这是对「未来」的查询，只有预先统计好才能 $O(1)$ 回答。

再按数组顺序（即数值非递减顺序）遍历每个 x，若 freq[x] == 0 说明这个数已经在之前被某次操作提前消耗掉了，直接跳过。为什么会出现被提前消耗：新开序列时一次性取走了 x+1 和 x+2，等外层循环走到它们时，配额已经用完，必须跳过而不是重复使用。

若 need[x] > 0，走接续分支：freq[x]--、need[x]--、need[x+1]++。为什么三个操作缺一不可：freq[x]-- 表示这个数被用掉；need[x]-- 表示一条承诺被兑现；need[x+1]++ 表示这条序列的结尾前移到了 x，现在改为等待 x+1。漏掉最后一句，序列就会凭空「断掉」。

否则走新开分支：先检查 freq[x+1] 和 freq[x+2] 是否都大于 0，任一为 0 就直接返回 false。为什么可以立即判负：x 既接不上任何已有序列，又凑不出长度 3 的新序列，而它又必须被使用，所以整个划分不可能成功，无需继续。

检查通过后把三个数各减 1，并令 need[x+3]++。为什么承诺记在 x+3 而不是 x+1：新序列已经占用了 x, x+1, x+2，它当前的结尾是 x+2，下一个能接的数是 x+3。

遍历结束返回 true。为什么不用检查 need 是否清空：need 中的每条承诺都对应一条长度已达 3 的合法序列，未被兑现只意味着该序列就此结束，不影响合法性；而所有元素是否用完由 freq 的扣减逻辑保证——每个元素要么在自己的轮次被消耗，要么被提前消耗后跳过。

以 nums = [1, 2, 3, 3, 4, 5] 走一遍。统计得 freq = {1:1, 2:1, 3:2, 4:1, 5:1}，need 为空。x = 1：freq[1] = 1 可用，need[1] = 0 无处可接，检查 freq[2] = 1、freq[3] = 2 都非零，于是三者各减 1 得 freq = {1:0, 2:0, 3:1, 4:1, 5:1}，并记 need[4] = 1（序列 [1,2,3] 建成，等着 4）。x = 2：freq[2] = 0，已被提前消耗，跳过。x = 3（第一个）：freq[3] = 1 可用，need[3] = 0 无处可接，检查 freq[4] = 1、freq[5] = 1 都非零，三者各减 1 得 freq 全零，并记 need[6] = 1（序列 [3,4,5] 建成）。x = 3（第二个）：freq[3] 已是 0，跳过。x = 4、x = 5：freq 均为 0，跳过。循环结束返回 true。最终划分是 [1,2,3] 与 [3,4,5]，两个 3 分属不同序列，恰好用完所有元素。注意 need[4] 那条承诺最后没被兑现，但序列 [1,2,3] 长度已达标，这正是「不必检查 need 清空」的直观体现。

代码实现

// 核心实现：哈希计数 + 贪心接龙，维护必要状态并避免重复处理。
class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.merge(x, 1, Integer::sum);
        }

        Map<Integer, Integer> need = new HashMap<>();
        for (int x : nums) {
            int cnt = freq.getOrDefault(x, 0);
            if (cnt == 0) {
                continue;
            }

            int needCnt = need.getOrDefault(x, 0);
            if (needCnt > 0) {
                freq.put(x, cnt - 1);
                need.put(x, needCnt - 1);
                need.merge(x + 1, 1, Integer::sum);
            } else {
                int c1 = freq.getOrDefault(x + 1, 0);
                int c2 = freq.getOrDefault(x + 2, 0);
                if (c1 == 0 || c2 == 0) {
                    return false;
                }
                freq.put(x, cnt - 1);
                freq.put(x + 1, c1 - 1);
                freq.put(x + 2, c2 - 1);
                need.merge(x + 3, 1, Integer::sum);
            }
        }

        return true;
    }
}

// 核心实现：哈希计数 + 贪心接龙，维护必要状态并避免重复处理。
func isPossible(nums []int) bool {
    freq := make(map[int]int)
    for _, x := range nums {
        freq[x]++
    }

    need := make(map[int]int)
    for _, x := range nums {
        if freq[x] == 0 {
            continue
        }

        if need[x] > 0 {
            freq[x]--
            need[x]--
            need[x+1]++
            continue
        }

        if freq[x+1] == 0 || freq[x+2] == 0 {
            return false
        }
        freq[x]--
        freq[x+1]--
        freq[x+2]--
        need[x+3]++
    }

    return true
}

复杂度分析

时间复杂度：$O(n)$。凭什么：第一趟统计频次是 n 次哈希写入；第二趟每个元素只被访问一次，分支内部是常数次哈希读写，没有嵌套循环也没有排序（输入已有序）。

空间复杂度：$O(n)$。凭什么：freq 和 need 两张哈希表的键数量都不超过数组中不同数值的个数，最坏为 n；没有额外的递归或队列。

关键点总结

把「记录完整对象」压缩成「记录对未来的承诺」是这题最值钱的抽象。已建成的序列只通过「结尾是几」影响后续，于是一张 need 表就替代了所有序列的显式存储，状态空间从指数降到线性。

贪心优先级要能论证：优先接续而非新开，理由是接续不产生新的「脆弱短序列」，也不额外消耗后续数值。面试里必须给出这条论证，只说「先接续就对了」会被认为在背结论。

不变量藏在设计里：因为新开序列时一次性消耗三个数，进入 need 的序列长度必然已经 ≥ 3。正是这个设计让结尾无需再做长度检查，也让「need 未清空不算失败」成立。设计数据结构时把约束前置，能省掉大量收尾判断。

已排序的输入是隐含前提，它保证「处理到 x 时比 x 小的都已安置完毕」。如果题目不保证有序，必须自己先排序，否则贪心的推进顺序被打乱，整套逻辑失效。

面试视角：这题还有一个用最小堆的经典解法——把每条序列按结尾值和长度入堆，优先接续结尾最小的。它更直观但要 $O(n \log n)$。能同时讲出两种并说明「计数版把堆换成了两张表，因为我们只需要计数而不需要按序取出」，是很好的加分点。

易错点总结

错误写法：接续分支里漏写 need[x+1]++；用例 nums = [1,2,3,4,5,6] → 建成 [1,2,3] 后 need[4] = 1，x = 4 接续时兑现了承诺却不再登记新承诺，x = 5 找不到可接的序列，只好新开却又缺 7，返回 false，正确答案是 true。

错误写法：跳过条件写成「当前值和上一个值相同就跳过」而不是查 freq[x] == 0；用例 nums = [1,2,3,3,4,5] → 第二个 3 被当成重复直接跳过，看似正确，但用例 nums = [1,2,3,4,5,6] 中所有值都不同，freq 已被提前消耗的 2、3 却不会被跳过，导致同一个数被用两次，返回错误的 true。

错误写法：新开序列时把承诺记在 need[x+1] 而不是 need[x+3]；用例 nums = [1,2,3,4,5] → 建成 [1,2,3] 后错误地登记「等待 2」，而 2 的配额早已用完，等外层走到 x = 4 时 need[4] 是 0，只能尝试新开 [4,5,6]，但 6 不存在，返回 false，正确答案是 true。

错误写法：优先新开序列而不是优先接续；用例 nums = [1,2,3,4,5] → x = 1 新开 [1,2,3]，x = 4 无处可接（因为 need 记的是 4，若先判新开则会尝试 [4,5,6] 而 6 不存在）直接返回 false，正确答案是 true（划分为 [1,2,3,4,5] 一条）。

错误写法：接续分支里忘记 need[x]--；用例 nums = [1,2,3,4,4] → 第一个 4 接到 [1,2,3] 之后承诺没被销账，第二个 4 误以为还有序列在等它，也走接续分支，返回 true；实际上 [1,2,3,4] 之外多出的那个 4 无处安放，正确答案是 false。

错误写法：用 map.get() 直接取值而不做缺省处理；用例 nums = [1,2,3] → 查询不存在的 need[1] 得到 null，Java 中拆箱抛空指针异常。

错误写法：遍历结束后额外检查 need 是否全为 0，不为 0 就返回 false；用例 nums = [1,2,3] → 建成一条长度 3 的序列后 need[4] = 1 仍挂着，被误判为失败，正确答案是 true。

错误写法：认为「同一个数值的多个副本可以出现在同一条序列里」；用例 nums = [1,2,2,3,3,4] → 若把两个 2 都接到同一条序列上，序列变成 [1,2,2,...] 不满足严格连续递增，实际正确划分是 [1,2,3] 和 [2,3,4]，返回 true。

错误写法：不先做一趟频次统计，改成边遍历边判断「后面还有没有 x+1」并现场向后扫描；用例大量重复元素 → 每次现场扫描退化成 $O(n^2)$ 超时。

错误写法：假设输入无序于是先做一次排序，却在排序后仍按原下标访问 freq；用例任意输入 → 索引与数值对不上，统计结果错乱。本题输入已保证有序，多余的排序既浪费时间又容易引入这类错位。

相似题目

题目	难度	考察点
128. 最长连续序列	中等	同样围绕「数值连续」做文章，但只需找最长的一段，靠哈希集合定位段首即可
621. 任务调度器	中等	也是频次驱动的贪心，但约束是同种元素的最小间隔而非连续递增
698. 划分为k个相等的子集	中等	同为「全部元素恰好分组」问题，但组内约束是和相等，贪心失效只能回溯搜索