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

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 快手
标签
数组 哈希表 贪心 堆（优先队列）

题目描述

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

image-20260929104504802

image-20260929104505048

题意分析

将非递减数组中的每个元素恰好分配给一个子序列，要求每条子序列相邻数值恰好相差 1，且长度至少为 3。相同数值可以分给不同序列，但不能在同一条连续递增序列里重复。

按升序处理尚未分配的数字：当前数字只能接在以它前一个数结尾的序列后，或者成为一条新序列的开头。需要判断这两种选择怎样才能保留后续划分的可能。

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

核心思路

[!blue]

用 freq[x] 记录尚未使用的数字 x 有多少份，用 need[x] 记录有多少条已经合法的序列以 x-1 结尾、可以继续接上 x。所有已建立序列都保证长度至少为 3，所以 need 只是延长机会，不是必须满足的长度欠账。

若 freq[x] == 0，当前这一份已经在更早创建新序列时被提前使用，直接跳过。否则，如果 need[x] > 0，优先延长一条旧序列：消耗一份 x，将一个接续机会从 need[x] 移到 need[x+1]。

优先接续不会损失解。若某个可行划分让旧序列停在 x-1，却从 x 新建了一条序列，可以把整条新序列接到旧序列后，仍连续且长度合格。若多条旧序列都能接 x，它们本身已满足最短长度，把从 x 开始的后缀转接给其中任意一条，也不会让其他旧序列变得不合法。因此无需为了新建序列而放弃当前可用的接续机会。

若没有旧序列能接 x，它就是尚未使用的最小数字，只能作为新序列的首项。为了保证最短长度，必须同时找到并消耗一份 x+1 和 x+2；任意一份不足都无法合法安排当前 x，应立即返回 false。创建成功后，新序列已合法，下一次可接的值是 x+3。

扫描结束时，所有元素都已分配，且新序列从建立起就至少包含三个连续数字，因此可以返回 true。此时 need 中仍有计数也没有关系，序列可以停在当前长度。

解题步骤

  1. 扫描数组，统计每个数值的剩余频次，初始化空的接续计数表。
  2. 按原有升序遍历数字 x，频次为零就跳过，避免重复使用预先消耗的元素。
  3. 有旧序列等待 x 时，消耗当前数字，并把对应接续机会改为 x+1。
  4. 否则检查 x+1、x+2 的剩余频次，足够就消耗三个数并增加 need[x+3]，不足则返回 false。
  5. 全部数字处理完后返回 true，不要求清空接续计数。

代码实现

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);
                // 新链已取得三个连续值，下一次可接续的位置是 x+3。
                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]--
        // 新链已取得三个连续值，下一次可接续的位置是 x+3。
        need[x+3]++
    }

    return true
}

复杂度分析

  • 时间复杂度：期望 $O(n)$。频次统计和分配各扫描一次，每次处理只进行常数次哈希表查询与更新。
  • 空间复杂度：$O(n)$。剩余频次和接续机会各保存至多线性数量的计数项。

关键点总结

[!green]

  • 已建立的序列都已经合法，接续只是延长它们，而不是修补长度不足的序列。
  • 优先接续可通过拼接或转接后缀保留可行划分；无法接续时，当前最小剩余值只能开新序列。
  • 新序列立即消耗三个连续数字，保证不会留下长度为一或二的未完成序列。
  • 重复值需要计数，不能只用集合记录数字或接续机会是否存在。

易错点总结

[!yellow]

  • 将 need 非空视为失败，会把已经足够长、无需再延长的合法序列错判掉。
  • 有接续机会却优先消耗后续两个数新建序列，可能挤占后面其他起点所需的数字。
  • 创建序列只消耗 x，却不确认 x+1、x+2，无法保证这条序列达到最短长度。
  • 遍历时不检查 freq[x]，会再次使用此前已被预取的数字。
  • 忽略数组已排序这一前提，会让当前值不再是最小剩余值，破坏无法接续时必须新建的判断。

相似题目

题目 难度 关联与区别
846. 一手顺子 中等 同样把所有数分成连续组，原题组长固定，本题组长至少3，因此优先延长已有序列。
128. 最长连续序列 中等 原题只求一段最长连续数值，本题必须消耗全部元素，并正确处理重复值的多条链。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/54464702
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！