LeetCode 846. 一手顺子

2026-09-13 HGNULB 约 4 分钟

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

分类

LeetCode 中等

题目描述

✅ 846. 一手顺子

题意分析

把全部牌分成若干组，每组恰有 groupSize 张，且牌值逐个连续，判断是否存在这样的分组。相同牌值的多张牌是独立资源，必须分别使用；不能留下多余牌。下面的排序会改变 hand 的原顺序。

解法：从最小剩余牌开始组成固定长度顺子

核心思路

[!blue]

先检查总牌数能否被组长整除，否则无论如何安排都不可能正好分完。之后将牌排序，用 counts[value] 记录每个值还有几张可用牌，不能用集合代替，因为同一个值可能需要出现在多组中。

从小到大扫描排序后的牌，遇到剩余数量为 0 的值就跳过；否则当前值 x 就是最小剩余牌。它不可能放在某组中间，因为那一组还需要更小的剩余牌，而这样的牌已经不存在。因此 x 必须是某组起点，这组只能由 x 到 x + groupSize - 1 各一张组成。

这说明贪心选择是被强制的：任何合法分组都必须包含这样一组。从各值中取走一张不会破坏其他可行方案，因为同值牌可以互换；取完后再处理剩余牌即可。若所需某个值已经没有余量，当前最小牌就无处可放，可以立即返回 false，不需要尝试其他起点。

内层每取一张牌就减少其频次。原数组中后续再次出现同值牌时，若还有余量就再开一组，否则跳过。扫描结束且没有失败，说明所有牌都已被分配到完整顺子，返回 true；groupSize = 1 时每张牌都能独立成组。

解题步骤

总牌数不能被组长整除时返回 false。

排序并用频次表保存每个值的剩余数量。

依次遇到仍有余量的最小值时，从它开始消耗一组连续牌。

组内缺少任意一张就返回 false，全部处理完则返回 true。

代码实现

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }

        Arrays.sort(hand);
        Map<Integer, Integer> counts = new HashMap<>();

        for (int value : hand) {
            counts.merge(value, 1, Integer::sum);
        }

        for (int start : hand) {
            if (counts.get(start) == 0) {
                continue;
            }

            for (int offset = 0; offset < groupSize; offset++) {
                int value = start + offset;
                int count = counts.getOrDefault(value, 0);

                if (count == 0) {
                    return false;
                }

                counts.put(value, count - 1);
            }
        }

        return true;
    }
}

import "sort"

func isNStraightHand(hand []int, groupSize int) bool {
    if len(hand)%groupSize != 0 {
        return false
    }
    sort.Ints(hand)
    counts := map[int]int{}
    for _, value := range hand {
        counts[value]++
    }
    for _, start := range hand {
        if counts[start] == 0 {
            continue
        }
        for offset := 0; offset < groupSize; offset++ {
            value := start + offset
            if counts[value] == 0 {
                return false
            }
            counts[value]--
        }
    }
    return true
}

复杂度分析

时间复杂度：$O(n\log n)$，n 为牌数。排序后的外层扫描为线性，所有内层成功迭代合计只消耗 n 张牌，失败时也只额外检查一个缺失值，因此哈希处理期望为 $O(n)$。

空间复杂度：频次表空间 $O(n)$。

关键点总结

[!green]

贪心不是任选一个起点，而是当前最小值的位置已经被强制确定。

易错点总结

[!yellow]

不能用集合代替频次表，重复牌可能组成多组。

最大值减最小值满足范围不代表中间没有缺牌。

groupSize=1 时每张牌单独成组，应返回 true。

相似题目

题目	难度	关联与区别
659. 分割数组为连续子序列	中等	同样使用剩余频次组成连续序列，但原题组长至少为 3，需优先续接已有序列；本题组长固定。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/18481129

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！