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.mdGiven 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.示例分析示例 1Input: 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 各出现两次分别被两个集合消费这说明同一数值可以出现在多个集合中计数是关键。示例 2Input: 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 均被多次使用但计数能够支撑因此整体可行。示例 3Input: 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] 1000000000nums长度可达 10 万nums[i]上限达 10 亿这直接排除了按值域开桶计数的做法值域太大也说明算法必须控制在O(n log n)或O(n)级别且计数结构必须使用哈希表而不是定长数组。解题思路排序 哈希计数 贪心消费README 中给出的核心思路是贪心算法共三步对nums升序排序对nums内数字进行哈希计数key数字value数量遍历nums中的数字以计数大于 0 的数字作为连续数字开头向后寻找 k 个连续数字若无法凑齐 k 个连续数字则返回false所有数字都能找到 k 个连续数字则返回true。为什么贪心是正确的关键在于每次固定使用当前未被消费的最小数字作为一组起点。由于所有集合要求是连续 k 个数字而排序后第一个未被消费的数字num不可能作为任何一组集合的中间元素因为它是最小的剩余数字任何以更小数字开头的集合已经处理完毕所以num必须是某个集合的起点该集合必然覆盖num, num1, ..., numk-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[numdiff] 0 { return false } mp[numdiff] - 1 } } return true }逐段解析计数阶段第一层for循环遍历numsmp[v] 1统计每个数字的出现次数。这里用map[int]int而非数组正是为了适配nums[i]高达 10 亿的值域约束。排序阶段sort.Ints(nums)原地升序排序。排序的意义在于之后按序遍历时总能拿到当前最小且未被消费完的数字作为新一组集合的起点。注意排序发生在计数之后两者互不影响顺序上也可以先排序再计数但先计数后排序的实现更直观。消费阶段外层for遍历排序后的nums。if mp[num] 0 { continue }跳过已被前面分组消费完的数字——这正是排序哈希配合的关键排序后同一个数字连续出现前一次消费会递减计数后续重复出现时若计数已归 0 则直接跳过。连续消费内层for diff : 0; diff k; diff从num开始向后检查num, num1, ..., numk-1共 k 个数字。只要任何一个mp[numdiff] 0说明无法凑齐一组连续 k 个数字立即返回false否则每个数字计数- 1完成一组消费。返回若遍历完所有数字都没有失败说明每个数字都被完整分组返回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 -covermodeatomic -coverprofilecoverage.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[numdiff] 0 { return false } mp[numdiff] - 1 } } return true }846 题的 README.md 描述的贪心思路与 1296 题一字不差升序排序、哈希计数、以计数大于 0 的数字作为顺子开头、找不到完整顺子即返回false846 题的约束为hand.length 10000、hand[i] 1000000000同样因值域过大而必须使用哈希计数。两题代码可以互相移植区别仅在函数名与参数名。刷题时可以把 846、1296 作为一组同题不同皮的组合题一起练习加深对贪心哈希模板的理解。小结要点说明核心思想贪心每次取当前最小未被消费的数字作为一组起点强制连续消费 k 个数字数据结构map[int]int哈希计数适配nums[i]达 10 亿的值域预处理sort.Ints升序排序保证能始终取到最小可用数字时间复杂度O(n log n)消费阶段总次数为O(n)空间复杂度O(n)边界长度不能被 k 整除时必然失败数字可重复需靠计数递减处理姊妹题846. Hand of Straights解法完全同构掌握了排序 哈希计数 贪心消费这一模板你就具备了解答 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考