
Info
数据结构精品课 和 递归算法专题课 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》 出版,签名版限时半价!
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
659. Split Array into Consecutive Subsequences | 659. 分割数组为连续子序列 | 🟠 |
斗地主中,大小连续的牌可以作为顺子,有时候我们把对子拆掉,结合单牌,可以组合出更多的顺子,可能更容易赢。
那么如何合理拆分手上的牌,合理地拆出顺子呢?我们今天看一道非常有意思的算法题,连续子序列的划分问题。
这是力扣第 659 题「分割数组为连续子序列」,题目很简单:
给你输入一个升序排列的数组 nums
(可能包含重复数字),请你判断 nums
是否能够被分割成若干个长度至少为 3 的子序列,每个子序列都由连续的整数组成。
函数签名如下:
// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
boolean isPossible(List<Integer> nums);
bool isPossible(vector<int>& nums);
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
def isPossible(nums: List[int]) -> bool
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
func isPossible(nums []int) bool {
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
var isPossible = function(nums) {};
比如题目举的例子,输入 nums = [1,2,3,3,4,4,5,5]
,算法返回 true。
因为 nums
可以被分割成 [1,2,3,4,5]
和 [3,4,5]
两个包含连续整数子序列。
但如果输入 nums = [1,2,3,4,4,5]
,算法返回 false,因为无法分割成两个长度至少为 3 的连续子序列。
对于这种涉及连续整数的问题,应该条件反射地想到排序,不过题目说了,输入的 nums
本就是排好序的。
那么,我们如何判断 nums
是否能够被划分成若干符合条件的子序列呢?
类似前文 回溯算法进行集合划分,我们想把 nums
的元素划分到若干个子序列中,其实就是下面这个代码逻辑:
for (int v : nums) {
if (...) {
// 将 v 分配到某个子序列中
} else {
// 实在无法分配 v
return false;
}
return true;
}
关键在于,我们怎么知道当前元素 v
如何进行分配呢?
肯定得分情况讨论,把情况讨论清楚了,题目也就做出来了。
总共有两种情况:
1、当前元素 v
自成一派,「以自己开头」构成一个长度至少为 3 的序列。
比如输入 nums = [1,2,3,6,7,8]
,遍历到元素 6
时,它只能自己开头形成一个符合条件的子序列 [6,7,8]
。
2、当前元素 v
接到已经存在的子序列后面。
比如输入 nums = [1,2,3,4,5]
,遍历到元素 4
时,它只能接到已经存在的子序列 [1,2,3]
后面。它没办法自成开头形成新的子序列,因为少了个 6
。
但是,如果这两种情况都可以,应该如何选择?
比如说,输入 nums = [1,2,3,4,5,5,6,7]
,对于元素 4
,你说它应该形成一个新的子序列 [4,5,6]
还是接到子序列 [1,2,3]
后面呢?
显然,nums
数组的正确划分方法是分成 [1,2,3,4,5]
和 [5,6,7]
,所以元素 4
应该优先判断自己是否能够接到其他序列后面,如果不行,再判断是否可以作为新的子序列开头。
这就是整体的思路,想让算法代码实现这两个选择,需要两个哈希表来做辅助:
freq
哈希表帮助一个元素判断自己是否能够作为开头,need
哈希表帮助一个元素判断自己是否可以被接到其他序列后面。
freq
记录每个元素出现的次数,比如 freq[3] == 2
说明元素 3
在 nums
中出现了 2 次。
那么如果我发现 freq[3], freq[4], freq[5]
都是大于 0 的,那就说明元素 3
可以作为开头组成一个长度为 3 的子序列。
need
记录哪些元素可以被接到其他子序列后面。
比如说现在已经组成了两个子序列 [1,2,3,4]
和 [2,3,4]
,那么 need[5]
的值就应该是 2,说明对元素 5
的需求为 2。
明白了这两个哈希表的作用,我们就可以看懂解法了:
// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
/**
* 检查序列是否可以被分成长度至少为 3 的连续子序列
* 每个子序列中不同的整数数量要相同
*
* @param nums 检查的序列
* @return 序列能够被组成子序列返回 true,否则返回 false
*/
public boolean isPossible(int[] nums) {
// 维护每个数在 nums 数组中出现的次数
HashMap<Integer, Integer> freq = new HashMap<>();
// 维护每个数作为结尾的连续子序列的需求量
HashMap<Integer, Integer> need = new HashMap<>();
// 遍历 nums 数组统计每个数在 nums 数组中出现的次数
for (int v : nums) freq.put(v, freq.getOrDefault(v, 0) + 1);
for (int v : nums) {
// 如果 v 已经被用到其他子序列中则无法再被用到
if (freq.get(v) == 0) {
continue;
}
// 尝试将 v 接到之前的某个序列后面
if (need.containsKey(v) && need.get(v) > 0) {
// v 可以接到之前的某个序列后面
freq.put(v, freq.get(v) - 1);
need.put(v, need.get(v) - 1);
need.put(v + 1, need.getOrDefault(v + 1, 0) + 1);
} else if (freq.containsKey(v) && freq.get(v) > 0 && freq.containsKey(v + 1) && freq.get(v + 1) > 0 && freq.containsKey(v + 2) && freq.get(v + 2) > 0) {
// 第二种情况,新建一个长度为 3 的子序列 [v, v+1, v+2]
freq.put(v, freq.get(v) - 1);
freq.put(v + 1, freq.get(v + 1) - 1);
freq.put(v + 2, freq.get(v + 2) - 1);
need.put(v + 3, need.getOrDefault(v + 3, 0) + 1);
} else {
// 两种情况都不符合,则无法分配
return false;
}
}
return true;
}
bool isPossible(vector<int>& nums) {
unordered_map<int, int> freq, need;
// 统计 nums 中元素的频率
for (int v : nums) freq[v]++;
for (int v : nums) {
if (freq[v] == 0) {
// 已经被用到其他子序列中
continue;
}
// 先判断 v 是否能接到其他子序列后面
if (need.count(v) && need[v] > 0) {
// v 可以接到之前的某个序列后面
freq[v]--;
// 对 v 的需求减一
need[v]--;
// 对 v + 1 的需求加一
need[v + 1]++;
} else if (freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0) {
// 将 v 作为开头,新建一个长度为 3 的子序列 [v,v+1,v+2]
freq[v]--;
freq[v + 1]--;
freq[v + 2]--;
// 对 v + 3 的需求加一
need[v + 3]++;
} else {
// 两种情况都不符合,则无法分配
return false;
}
}
return true;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
def isPossible(nums: List[int]) -> bool:
# 使用字典统计 nums 中元素的频率
freq, need = {}, {}
for v in nums:
freq[v] = freq.get(v, 0) + 1
for v in nums:
if freq[v] == 0:
# 已经被用到其他子序列中
continue
if v in need and need[v] > 0:
# v 可以接到之前的某个序列后面
freq[v] -= 1
need[v] -= 1
need[v + 1] = need.get(v + 1, 0) + 1
elif freq[v] > 0 and freq.get(v + 1, 0) > 0 and freq.get(v + 2, 0) > 0:
# 将 v 作为开头,新建一个长度为 3 的子序列 [v,v+1,v+2]
freq[v] -= 1
freq[v + 1] -= 1
freq[v + 2] -= 1
need[v + 3] = need.get(v + 3, 0) + 1
else:
# 两种情况都不符合,则无法分配
return False
return True
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
func isPossible(nums []int) bool {
freq, need := make(map[int]int), make(map[int]int)
// 统计 nums 中元素的频率
for _, v := range nums {
freq[v]++
}
for _, v := range nums {
if freq[v] == 0 {
// 已经被用到其他子序列中
continue
}
// 先判断 v 是否能接到其他子序列后面
if n, ok := need[v]; ok && n > 0 {
// v 可以接到之前的某个序列后面
freq[v]--
// 对 v 的需求减一
need[v]--
// 对 v + 1 的需求加一
need[v + 1]++
} else if freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0 {
// 将 v 作为开头,新建一个长度为 3 的子序列 [v,v+1,v+2]
freq[v]--
freq[v + 1]--
freq[v + 2]--
// 对 v + 3 的需求加一
need[v + 3]++
} else {
// 两种情况都不符合,则无法分配
return false
}
}
return true
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
var isPossible = function(nums) {
var freq = {};
var need = {};
// 统计 nums 中元素的频率
for (var i = 0; i < nums.length; i++) {
var v = nums[i];
if (v in freq) {
freq[v]++;
} else {
freq[v] = 1;
}
}
for (var i = 0; i < nums.length; i++) {
var v = nums[i];
if (freq[v] == 0) {
// 已经被用到其他子序列中
continue;
}
// 先判断 v 是否能接到其他子序列后面
if (v in need && need[v] > 0) {
// v 可以接到之前的某个序列后面
freq[v]--;
// 对 v 的需求减一
need[v]--;
// 对 v + 1 的需求加一
if (need[v + 1]) {
need[v + 1]++;
} else {
need[v + 1] = 1;
}
} else if (freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0) {
// 将 v 作为开头,新建一个长度为 3 的子序列 [v,v+1,v+2]
freq[v]--;
freq[v + 1]--;
freq[v + 2]--;
// 对 v + 3 的需求加一
if (need[v + 3]) {
need[v + 3]++;
} else {
need[v + 3] = 1;
}
} else {
// 两种情况都不符合,则无法分配
return false;
}
}
return true;
};
至此,这道题就解决了。
那你可能会说,斗地主里面顺子至少要 5 张连续的牌,我们这道题只计算长度最小为 3 的子序列,怎么办?
很简单,把我们的 else if 分支修改一下,连续判断 v
之后的连续 5 个元素就行了。
那么,我们再难为难为自己,如果我想要的不只是一个布尔值,我想要你给我把子序列都打印出来,怎么办?
其实这也很好实现,只要修改 need
,不仅记录对某个元素的需求个数,而且记录具体是哪些子序列产生的需求:
// need[6] = 2 说明有两个子序列需要 6
unordered_map<int, int> need;
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// 记录哪两个子序列需要 6
unordered_map<int, vector<vector<int>>> need;
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// need[6] = 2 说明有两个子序列需要 6
unordered_map<int, int> need;
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// 记录哪两个子序列需要 6
unordered_map<int, vector<vector<int>>> need;
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
# need[6] = 2 说明有两个子序列需要 6
need = {}
# need[6] = [
# [3,4,5],
# [2,3,4,5],
# ]
# 记录哪两个子序列需要 6
need = {}
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// need[6] = 2 说明有两个子序列需要 6
need := make(map[int]int)
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// 记录哪两个子序列需要 6
need := make(map[int][][]int)
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var need = new Map(); // or {}
need.set(6, 2); // 说明有两个子序列需要 6
var need = new Map(); // or {}
need.set(6, [
[3, 4, 5],
[2, 3, 4, 5]
]);
// 记录哪两个子序列需要 6
这样,我们稍微修改一下之前的代码就行了:
// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
/**
* 检查给定的数组是否可以分割成若干子序列,要求每个子序列长度 >= 3,
* 相同数字不能出现在同一个子序列中。
*
* 思路:贪心 + 哈希表,以哈希表 {number: frequency} 维护每个数字出现的频率,
* 再以哈希表 {end: list} 维护每个以 end 为结尾的子序列,
* 尝试向已有的子序列中添加数字,若没有已有子序列,尝试在 nums 中新建一个包含
* 连续的三个数的子序列。
*
* 时间复杂度:O(N)
* 空间复杂度:O(N)
*/
public boolean isPossible(int[] nums) {
// 统计每个数字出现的频率
Map<Integer, Integer> freq = new HashMap<>();
for (int v : nums) freq.put(v, freq.getOrDefault(v, 0) + 1);
// 以哈希表 {end: list} 维护每个以 end 为结尾的子序列
Map<Integer, List<List<Integer>>> need = new HashMap<>();
for (int v : nums) {
if (freq.get(v) == 0) {
continue;
}
if (need.containsKey(v) && !need.get(v).isEmpty()) {
// 如果已经存在以 v - 1 结尾的子序列,就将当前 v 接到它后面
freq.put(v, freq.get(v) - 1);
// 取出需要 v 的最短子序列
List<Integer> seq = need.get(v).remove(need.get(v).size() - 1);
seq.add(v);
// 将更新后的子序列添加到 map 中
if (!need.containsKey(v + 1)) {
need.put(v + 1, new ArrayList<>());
}
need.get(v + 1).add(seq);
} else if (freq.get(v) > 0 && freq.getOrDefault(v + 1, 0) > 0
&& freq.getOrDefault(v + 2, 0) > 0) {
// 否则如果存在 v, v + 1, v + 2,就新建一个以 v, v + 1, v + 2 为顺序的子序列
freq.put(v, freq.get(v) - 1);
freq.put(v + 1, freq.get(v + 1) - 1);
freq.put(v + 2, freq.get(v + 2) - 1);
List<Integer> seq = new ArrayList<>();
seq.add(v);
seq.add(v + 1);
seq.add(v + 2);
// 将更新后的子序列添加到 map 中
if (!need.containsKey(v + 3)) {
need.put(v + 3, new ArrayList<>());
}
need.get(v + 3).add(seq);
} else {
// 如果既没有可以接到的子序列,也无法新建新的子序列,则返回 false
return false;
}
}
// 遍历所有序列,检查它们的长度是否都大于等于 3,如果有一个短于 3 则返回 false
for (List<List<Integer>> allSeq : need.values()) {
for (List<Integer> seq : allSeq) {
if (seq.size() < 3) {
return false;
}
}
}
// 如果所有序列长度都大于等于 3,则返回 true
return true;
}
bool isPossible(vector<int>& nums) {
unordered_map<int, int> freq;
unordered_map<int, vector<vector<int>>> need;
for (int v : nums) freq[v]++;
for (int v : nums) {
if (freq[v] == 0) {
continue;
}
if (need.count(v) && need[v].size() > 0) {
// v 可以接到之前的某个序列后面
freq[v]--;
// 随便取一个需要 v 的子序列
vector<int> seq = need[v].back();
need[v].pop_back();
// 把 v 接到这个子序列后面
seq.push_back(v);
// 这个子序列的需求变成了 v + 1
need[v + 1].push_back(seq);
} else if (freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0) {
// 可以将 v 作为开头
freq[v]--;
freq[v + 1]--;
freq[v + 2]--;
// 新建一个长度为 3 的子序列 [v,v + 1,v + 2]
vector<int> seq{v, v + 1, v + 2};
// 对 v + 3 的需求加一
need[v + 3].push_back(seq);
} else {
return false;
}
}
// 打印切分出的所有子序列
for (auto it : need) {
for (vector<int>& seq : it.second) {
for (int v : seq) {
cout << v << " ";
}
cout << endl;
}
}
return true;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
from typing import List
# 定义函数isPossible,参数为一个整型列表,返回值为布尔型
def isPossible(nums: List[int]) -> bool:
# 定义标准型字典freq,来统计nums中元素出现的次数
freq = {}
# 定义映射型字典need,来记录nums中元素可以组成的子序列
need = {}
# 统计nums中元素的出现次数
for v in nums:
freq[v] = freq.get(v, 0) + 1
# 遍历nums中的元素
for v in nums:
# 如果 freq[v] 为0,则跳过
if freq[v] == 0:
continue
# 如果need中有以v为结尾的子序列,则将v接到最后一个序列之后
if v in need and len(need[v]) > 0:
# 减少v的出现次数
freq[v] -= 1
# 取出需要v的子序列
seq = need[v].pop()
# 将v加到该子序列最后
seq.append(v)
# 设置需求为v+1子序列中
need[v+1] = need.get(v+1, []) + [seq]
# 如果由 v,v+1, v+2 三个元素组成的子序列在freq中都出现
elif freq[v] > 0 and freq.get(v+1, 0) > 0 and freq.get(v+2, 0) > 0:
# 减小 v, v+1, v+2 出现的次数
freq[v] -= 1
freq[v+1] -= 1
freq[v+2] -= 1
# 新建一个由v, v+1, v+2组成的子序列
seq = [v, v+1, v+2]
# v+3子序列需要加入以后的子序列列表中
need[v+3] = need.get(v+3, []) + [seq]
else:
return False
# 打印出路径
for k, v in need.items():
for seq in v:
for num in seq:
print(num, end=' ')
print()
return True
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
// Convert this CPP code to Go.
// Don't modify Chinese comments, you should retain them.
// Restore all the comments in your code.
func isPossible(nums []int) bool {
// 使用两个map,一个记录每个数字的数量,一个记录需要哪些子序列
freq := make(map[int]int)
need := make(map[int][][]int)
// 统计频率
for _, v := range nums {
freq[v]++
}
// 遍历数组
for _, v := range nums {
// 如果已经被凑成子序列了,跳过
if freq[v] == 0 {
continue
}
// 如果可以接到之前的某个序列后面
if n, ok := need[v]; ok && len(n) > 0 {
// 减去一个 v
freq[v]--
// 随便取一个需要 v 的子序列
seq := need[v][len(need[v])-1]
need[v] = need[v][:len(need[v])-1]
// 把 v 接到这个子序列后面
seq = append(seq, v)
// 这个子序列的需求变成了 v + 1
need[v+1] = append(need[v+1], seq)
// 如果可以将 v 作为开头
} else if freq[v] > 0 && freq[v+1] > 0 && freq[v+2] > 0 {
// 都减去一次即可
freq[v]--
freq[v+1]--
freq[v+2]--
// 新建一个长度为 3 的子序列 [v, v + 1, v + 2]
need[v+3] = append(need[v+3], []int{v, v + 1, v + 2})
} else {
return false
}
}
// 打印所有子序列
for k, v := range need {
for _, seq := range v {
for _, sub := range seq {
fmt.Printf("%d ", sub)
}
fmt.Println()
}
}
return true
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 cpp 代码对比查看。
var isPossible = function(nums) {
var freq = new Map();
var need = new Map();
nums.forEach(function(v) {
freq.set(v, freq.get(v) + 1 || 1);
});
for (var i = 0; i < nums.length; i++) {
var v = nums[i];
if (freq.get(v) == 0) {
continue;
}
if (need.has(v) && need.get(v).length > 0) {
// v 可以接到之前的某个序列后面
var seq = need.get(v)[need.get(v).length - 1];
need.get(v).pop();
// 把 v 接到这个子序列后面
seq.push(v);
// 这个子序列的需求变成了 v + 1
if (!need.has(v + 1)) {
need.set(v + 1, []);
}
need.get(v + 1).push(seq);
} else if (freq.get(v) > 0 && freq.get(v + 1) > 0 && freq.get(v + 2) > 0) {
// 可以将 v 作为开头
freq.set(v, freq.get(v) - 1);
freq.set(v + 1, freq.get(v + 1) - 1);
freq.set(v + 2, freq.get(v + 2) - 1);
// 新建一个长度为 3 的子序列 [v,v + 1,v + 2]
var seq = [v, v + 1, v + 2];
// 对 v + 3 的需求加一
if (!need.has(v + 3)) {
need.set(v + 3, []);
}
need.get(v + 3).push(seq);
} else {
return false;
}
}
// 打印切分出的所有子序列
need.forEach(function(value, key) {
value.forEach(function(seq) {
console.log(seq.join(" "));
});
});
return true;
};
这样,我们记录具体子序列的需求也实现了。
如果本文对你有帮助,点个赞,微信会给你推荐更多相似文章。
《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复「全家桶」可下载配套 PDF 和刷题全家桶:

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释