LeetCode 剑指 Offer 61. 扑克牌中的顺子
目录
题目描述
题意分析
输入固定是 5 张牌，问它们能不能凑成 5 个连续的点数。牌面用
0表示大小王，它是万能牌，可以当成任意点数；其余牌是1到13的实际点数。返回值只是一个布尔量，不需要给出具体是哪一段连续序列。
约束里有几个直接可用的信号：数组长度恒为5，所以任何做法的规模都是常数；牌面范围0到13很窄，可以用定长桶或集合承载；万能牌只有0这一种表示，不需要区分大王小王。
边界要事先想清楚三点：万能牌本身之间「重复」是允许的，两张0完全合法；非万能牌之间一旦重复，无论多少万能牌都补不回来，因为顺子里每个点数只能出现一次；题目里A就是1，不存在把A接到K后面的环形顺子。
解法：排序后检查重复和跨度
核心思路
大小王
0可以填补任意缺口，所以不必枚举它们分别代表什么。真正决定能否组成顺子的只有两个条件：非零牌不能重复，并且最大非零牌与最小非零牌的差小于 5。先排序，所有
0会集中在开头，相同的非零牌会相邻，最大牌位于末尾。跳过0后，扫描相邻非零牌即可判重，再用首尾计算跨度。这两个条件既必要也充分：顺子的五个点数互不相同，极差一定是 4，所以重复或跨度至少为 5 都不可能；反过来，若非零牌互异且跨度小于 5，它们一定能放进某个长度为 5 的连续区间，剩余空位由
0补齐。扫描时的不变量是：
[first, i]内已经检查过的非零牌严格递增。因此循环结束后不存在重复，而排序后的首尾值就是全局最小值和最大值，最终跨度判断即可给出答案。
解题步骤
- 将 5 张牌升序排序。
- 移动
first，跳过开头所有0；若全是0，直接返回true。- 从第二张非零牌开始比较相邻元素，发现重复立即返回
false。- 判断
nums[last] - nums[first] < 5，成立则所有缺口都能由大小王补齐。例如
[0,0,1,2,5]没有非零重复，跨度为5 - 1 = 4，两张王补 3、4 后可组成顺子；[0,1,2,2,5]有重复的 2，即使有王也无法消除重复。
代码实现
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int first = 0;
while (first < nums.length && nums[first] == 0) {
first++;
}
if (first == nums.length) {
return true;
}
for (int i = first + 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
return false;
}
}
return nums[nums.length - 1] - nums[first] < 5;
}
}
import "sort"
func isStraight(nums []int) bool {
sort.Ints(nums)
first := 0
for first < len(nums) && nums[first] == 0 {
first++
}
if first == len(nums) {
return true
}
for i := first + 1; i < len(nums); i++ {
if nums[i] == nums[i-1] {
return false
}
}
return nums[len(nums)-1]-nums[first] < 5
}
复杂度分析
- 时间复杂度：
O(1)。本题固定只有 5 张牌；若推广到n张，排序主导为O(n log n)。- 空间复杂度：
O(1)。牌数固定，排序所需的辅助空间有常数上界。
关键点总结
- 万能牌只负责补缺口，不参与重复判断，也不能作为最小牌计算跨度。
- 五个连续整数的极差是 4，所以条件是
max - min < 5，不是<= 5。- 「非零牌不重复 + 跨度小于 5」是充要条件，回答时要把充分性也讲清楚。
- 排序会修改输入数组；若调用方要求保留原顺序，再改用定长布尔数组判重并同步维护最大、最小值。
易错点总结
- 把
0算进跨度：[0,0,1,2,5]会被误算为跨度 5，从而错判为false。- 把多个
0当成重复牌：大小王之间可以重复，重复检查必须从第一张非零牌开始。- 边界写成
max - min <= 5：[1,2,3,4,6]会被错判为顺子，正确上限是 4。- 只检查跨度、不检查重复：
[0,1,2,2,3]跨度很小，但重复的 2 无法出现在顺子中。- 全为
0时访问nums[first]：first == nums.length会越界，应先返回true。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 128. 最长连续序列 | 中等 | 求最长连续段长度，无通配符且需哈希加速 |
| 217. 存在重复元素 | 简单 | 只做重复判定，是本题第一个条件的独立版本 |
| 219. 存在重复元素 II | 简单 | 重复判定附加下标距离限制 |
| 228. 汇总区间 | 简单 | 有序数组按连续性切段并输出区间 |
| 1228. 等差数列中缺失的数字 | 简单 | 已知公差求唯一缺项，缺口只有一个且必须补准 |
| LCR 119. 最长连续序列 | 中等 | 最长连续序列换编号，考察去重与端点判定 |