企业官网建设流程全解析

LeetCode-Go 题解 1296：贪心算法划分 K 个连续数字集合（Divide Array in Sets of K Consecutive Numbers）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode 第 1296 题「Divide Array in Sets of K Consecutive Numbers」为核心，深入讲解如何判断一个整数数组能否被划分为若干组由 k 个连续数字组成的集合。文章完整继承仓库 leetcode/1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers/README.md 中的题目描述、示例、约束与贪心解题思路，并结合仓库内的 Go 源码实现与测试用例，剖析"排序 + 哈希计数 + 贪心消费"的完整链路。读完本文，你将掌握这类"连续分组可行性判定"问题的通用贪心模板，并能独立分析其时间复杂度、正确性边界以及与 846 题的等价关系。

题目：能否把数组划分成 k 个连续数字的集合

给定一个整数数组nums和一个正整数k，判断是否可以把该数组划分成若干组，使得每组恰好包含 k 个连续递增的数字。如果可以，返回true，否则返回false。

题目原文（见 README.md）：

Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers. Return true if it is possible. Otherwise, return false.

示例分析

示例 1：

Input: nums = [1,2,3,3,4,4,5,6], k = 4 Output: true Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

nums中共 8 个元素，恰好组成 2 组、每组 4 个连续数字。注意数字 3、4 各出现两次，分别被两个集合消费，这说明同一数值可以出现在多个集合中，计数是关键。

示例 2：

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 Output: true Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

12 个元素划分为 4 组、每组 3 个连续数字。[1,2,3]、[2,3,4]、[3,4,5]之间存在数字重叠（2、3、4 均被多次使用），但计数能够支撑，因此整体可行。

示例 3：

Input: nums = [1,2,3,4], k = 3 Output: false Explanation: Each array should be divided in subarrays of size 3.

4 个元素无法整除 3，无论怎么划分都不满足"每组恰好 3 个"的要求。

约束条件

- 1 <= k <= nums.length <= 100000 - 1 <= nums[i] <= 1000000000

nums长度可达 10 万，nums[i]上限达 10 亿，这直接排除了"按值域开桶计数"的做法（值域太大），也说明算法必须控制在O(n log n)或O(n)级别，且计数结构必须使用哈希表而不是定长数组。

解题思路：排序 + 哈希计数 + 贪心消费

README 中给出的核心思路是贪心算法，共三步：

1. 对nums升序排序；
2. 对nums内数字进行哈希计数（key：数字，value：数量）；
3. 遍历nums中的数字，以计数大于 0 的数字作为连续数字开头，向后寻找 k 个连续数字；若无法凑齐 k 个连续数字则返回false；
4. 所有数字都能找到 k 个连续数字则返回true。

为什么贪心是正确的

关键在于每次固定使用当前未被消费的最小数字作为一组起点。由于所有集合要求是"连续 k 个数字"，而排序后第一个未被消费的数字num不可能作为任何一组集合的中间元素（因为它是最小的剩余数字，任何以更小数字开头的集合已经处理完毕），所以num必须是某个集合的起点，该集合必然覆盖num, num+1, ..., num+k-1。若其中任何一个数字计数不足，则整体不可行；反之，一次性消耗这 k 个数字后继续处理下一个最小数字，最终即可判定全局可行性。

这种"每次固定取最小元素、强制连续消费"的策略是典型的贪心：局部最优（最小数字必须作起点）即全局最优（不存在更优的分组方式）。

边界条件讨论

• 整除性检查：若len(nums) % k != 0，显然不可能划分，可直接返回false。README 中的实现没有显式写出该检查，但贪心逻辑本身会自然失败——最后剩余不足 k 个数字时，内层循环必然遇到计数为 0 的元素而返回false。显式提前检查可以让代码更早退出、语义更清晰。
• 数字可以重复：哈希计数的 value 记录每个数字出现的次数，每次消费递减 1，计数归 0 表示该数字已全部被分组完毕。
• 值域很大：nums[i]最大 10 亿，不能用数组下标计数，必须用map[int]int。

源码实现：一行行拆解贪心消费过程

仓库中的核心实现位于 1296.Divide Array in Sets of K Consecutive Numbers.go，与 README 中的代码完全一致：

package leetcode import "sort" func isPossibleDivide(nums []int, k int) bool { mp := make(map[int]int) for _, v := range nums { mp[v] += 1 } sort.Ints(nums) for _, num := range nums { if mp[num] == 0 { continue } for diff := 0; diff < k; diff++ { if mp[num+diff] == 0 { return false } mp[num+diff] -= 1 } } return true }

逐段解析：

1. 计数阶段：第一层for循环遍历nums，mp[v] += 1统计每个数字的出现次数。这里用map[int]int而非数组，正是为了适配nums[i]高达 10 亿的值域约束。

2. 排序阶段：sort.Ints(nums)原地升序排序。排序的意义在于，之后按序遍历时总能拿到"当前最小且未被消费完"的数字作为新一组集合的起点。注意排序发生在计数之后，两者互不影响，顺序上也可以先排序再计数，但先计数后排序的实现更直观。

3. 消费阶段：外层for遍历排序后的nums。if mp[num] == 0 { continue }跳过已被前面分组消费完的数字——这正是排序+哈希配合的关键：排序后同一个数字连续出现，前一次消费会递减计数，后续重复出现时若计数已归 0 则直接跳过。

4. 连续消费：内层for diff := 0; diff < k; diff++从num开始向后检查num, num+1, ..., num+k-1共 k 个数字。只要任何一个mp[num+diff] == 0，说明无法凑齐一组连续 k 个数字，立即返回false；否则每个数字计数-= 1，完成一组消费。

5. 返回：若遍历完所有数字都没有失败，说明每个数字都被完整分组，返回true。

算法复杂度

• 时间复杂度：O(n log n)。排序占主导；计数遍历与消费遍历均为O(n)。虽然内层循环每次消耗 k 个数字，但每个数字最多被消费一次，因此消费阶段整体仍是O(n)而非O(n·k)——这一点是分析该实现复杂度时的关键：总消费次数等于数组长度。
• 空间复杂度：O(n)。哈希表最多存储n个不同数字的计数。

正确性验证：结合测试用例

仓库的测试文件 1296.Divide Array in Sets of K Consecutive Numbers_test.go 中，Test_Problem1296完整覆盖了 README 中的三个示例：

qs := []question1296{ { para1296{[]int{1, 2, 3, 3, 4, 4, 5, 6}, 4}, ans1296{true}, }, { para1296{[]int{3, 2, 1, 2, 3, 4, 3, 4, 5, 9, 10, 11}, 3}, ans1296{true}, }, { para1296{[]int{1, 2, 3, 4}, 3}, ans1296{false}, }, }

三个用例分别覆盖：可行且数字有重叠、可行且分组较多、不可行（长度不能被 k 整除）三类典型场景，与 LeetCode 官方给出的示例一一对应。测试通过isPossibleDivide(p.nums, p.k)直接断言函数输出，可用于本地回归验证。

本地运行验证

项目根目录的 gotest.sh 提供了统一的测试入口：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

如需单独验证本题，可在项目根目录执行：

go test -v -run Test_Problem1296 ./leetcode/1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers/

项目 go.mod 声明module github.com/halfrost/LeetCode-Go与go 1.19，上述测试命令在该环境下可直接运行。

姊妹题：846. Hand of Straights（一手顺子）

本题与 LeetCode 第 846 题「Hand of Straights（一手顺子）」是完全同构的题目：846 题把数组换成 Alice 手中的扑克牌hand、k换成每组牌数groupSize，判定能否把牌分成若干组、每组由groupSize张连续牌组成。两题只差一个名字，核心语义一致。

仓库中 846.Hand of Straights.go 的实现与本题几乎逐行相同：

func isNStraightHand(hand []int, groupSize int) bool { mp := make(map[int]int) for _, v := range hand { mp[v] += 1 } sort.Ints(hand) for _, num := range hand { if mp[num] == 0 { continue } for diff := 0; diff < groupSize; diff++ { if mp[num+diff] == 0 { return false } mp[num+diff] -= 1 } } return true }

• 846 题的 README.md 描述的贪心思路与 1296 题一字不差：升序排序、哈希计数、以计数大于 0 的数字作为顺子开头、找不到完整顺子即返回false；
• 846 题的约束为hand.length <= 10000、hand[i] <= 1000000000，同样因值域过大而必须使用哈希计数。

两题代码可以互相移植，区别仅在函数名与参数名。刷题时可以把 846、1296 作为一组"同题不同皮"的组合题一起练习，加深对贪心+哈希模板的理解。

小结

掌握了"排序 + 哈希计数 + 贪心消费"这一模板，你就具备了解答 1296、846 这类"连续分组可行性判定"问题的通用能力。核心代码仅 20 余行，但背后涵盖了排序预处理、哈希计数的空间策略选择、贪心正确性论证与复杂度分析四个关键环节，值得反复推敲。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go