LeetCode 2849 解法精讲：将数组划分为最大差值不超过 k 的三元组（排序与计数排序双方案）

LeetCode 2849 解法精讲将数组划分为最大差值不超过 k 的三元组排序与计数排序双方案【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于 NeetCode 题解仓库中的文章 divide-array-into-arrays-with-max-difference.md 展开围绕“把长度是 3 的倍数的整数数组划分成若干三元组使得每组最大值与最小值之差 k”这一经典分组问题完整讲解两种可行方案——基于排序的贪心分组、基于计数排序的线性扫描——的直觉、算法步骤、多语言实现与复杂度差异并深入剖析三类高频错误。读完后你不仅能写出这道题的正确解法还能掌握“排序 贪心分组”这一类问题的通用判定套路。问题背景与前置知识原题LeetCode 2849. Divide Array Into Arrays of Length Three的约束为给定整数数组numsnums.length是 3 的倍数1 k 10^9要求把数组划分成若干个长度为 3 的组每组最大与最小元素之差不超过k若不存在这样的划分则返回空数组分组顺序与组内元素顺序任意。原文档articles/divide-array-into-arrays-with-max-difference.md在 Prerequisites 一节列出的前置知识为排序算法Sorting Algorithms——理解排序如何把相近的元素聚拢在一起服务于分组类问题贪心算法Greedy Algorithms——通过局部最优选择把排序后相邻的三个元素编为一组达成全局最优计数排序Counting Sort——当取值范围受限时一种 O(n k) 的排序技巧。这三个前置点正是全文两条技术路线的基础方案一依赖比较排序 贪心方案二依赖值域有界时的计数排序。方案一排序 贪心分组直觉为什么“排序后按顺序三个一组”就是最优策略原文档给出的核心直觉是为了让每个三元组内部的差值尽可能小应该把数值接近的元素放在一起排序天然实现了这一点。排序之后贪心地把每三个相邻元素编为一组对每组只需检查最大与最小元素之差即三元组中第一与第三个元素之差是否 k。只要有任何一组不满足就不存在任何合法的划分——这一定理是整个贪心策略成立的根基。从源码结构看所有语言的实现都只依赖一个判定条件nums[i 2] - nums[i] k没有任何回溯或重新组合逻辑说明该贪心是“可判定即成立”的强贪心若排序后的固定三连组都满足约束则方案直接成立若某一组不满足则任何别的划分方式也必然失败可推断其论证方式为排序后该“断档”处的元素无论如何跨组重配都会把更大的跨度塞进某个三元组。算法步骤将数组升序排序以步长3遍历数组对每组三个连续元素检查nums[i 2] - nums[i] k若条件被违反返回空数组否则将该三元组加入结果返回所有三元组组成的列表。多语言实现Pythonclass Solution: def divideArray(self, nums: List[int], k: int) - List[List[int]]: nums.sort() res [] for i in range(0, len(nums), 3): if nums[i 2] - nums[i] k: return [] res.append(nums[i: i 3]) return resJavapublic class Solution { public int[][] divideArray(int[] nums, int k) { Arrays.sort(nums); int[][] res new int[nums.length / 3][3]; for (int i 0, idx 0; i nums.length; i 3, idx) { if (nums[i 2] - nums[i] k) { return new int[][]{}; } res[idx][0] nums[i]; res[idx][1] nums[i 1]; res[idx][2] nums[i 2]; } return res; } }Cclass Solution { public: vectorvectorint divideArray(vectorint nums, int k) { sort(nums.begin(), nums.end()); vectorvectorint res; for (int i 0; i nums.size(); i 3) { if (nums[i 2] - nums[i] k) { return {}; } res.push_back({nums[i], nums[i 1], nums[i 2]}); } return res; } };JavaScript注意必须传入比较函数(a, b) a - b否则默认按字典序排序class Solution { divideArray(nums, k) { nums.sort((a, b) a - b); const res []; for (let i 0; i nums.length; i 3) { if (nums[i 2] - nums[i] k) { return []; } res.push([nums[i], nums[i 1], nums[i 2]]); } return res; } }Gofunc divideArray(nums []int, k int) [][]int { sort.Ints(nums) res : [][]int{} for i : 0; i len(nums); i 3 { if nums[i2]-nums[i] k { return [][]int{} } res append(res, []int{nums[i], nums[i1], nums[i2]}) } return res }Kotlinclass Solution { fun divideArray(nums: IntArray, k: Int): ArrayIntArray { nums.sort() val res mutableListOfIntArray() for (i in nums.indices step 3) { if (nums[i 2] - nums[i] k) { return emptyArray() } res.add(intArrayOf(nums[i], nums[i 1], nums[i 2])) } return res.toTypedArray() } }Swiftclass Solution { func divideArray(_ nums: [Int], _ k: Int) - [[Int]] { let nums nums.sorted() var res [[Int]]() for i in stride(from: 0, to: nums.count, by: 3) { if nums[i 2] - nums[i] k { return [] } res.append([nums[i], nums[i 1], nums[i 2]]) } return res } }Rustmut nums声明用于原地排序impl Solution { pub fn divide_array(mut nums: Veci32, k: i32) - VecVeci32 { nums.sort(); let mut res Vec::new(); for i in (0..nums.len()).step_by(3) { if nums[i 2] - nums[i] k { return vec![]; } res.push(vec![nums[i], nums[i 1], nums[i 2]]); } res } }C#public class Solution { public int[][] DivideArray(int[] nums, int k) { Array.Sort(nums); int[][] res new int[nums.Length / 3][]; for (int i 0, idx 0; i nums.Length; i 3, idx) { if (nums[i 2] - nums[i] k) { return new int[][] {}; } res[idx] new int[] { nums[i], nums[i 1], nums[i 2] }; } return res; } }从各语言实现的结构看值得注意的细节有两点一是 Java/C# 版本预先按nums.Length / 3分配了二维数组容量题目保证长度是 3 的倍数避免了动态扩容二是所有语言在违规时都返回“空数组”而非nullJava 中写作new int[][]{}这与后文“返回值处理”一节的坑点严格对应。时间/空间复杂度原文档给出的结论时间复杂度$O(n \log n)$由排序主导分组扫描仅为 $O(n)$空间复杂度$O(n)$用于存放输出数组各语言排序本身的栈开销通常不计入或视实现而定。方案二计数排序值域受限时线性化直觉把“排序”换成“按值扫描”当数值范围受限时比较排序的 $\log n$ 因子是可以省掉的。原文档的直觉是统计每个数出现的次数然后按数值从小到大的顺序“展开”这些元素一边展开一边攒组每当攒满 3 个元素就校验组内最大值与最小值之差是否 k。由于“按值扫描”本身就等价于一次排序整个流程可以接近线性完成。算法步骤求出数组最大值创建count数组统计每个数字的出现次数从0遍历到最大值对每个仍有剩余计数的数字将其加入当前组当组大小达到3时检查group[2] - group[0] k若是则返回空数组否则将该组加入结果并开启新组返回所有组。多语言实现要点版Pythonclass Solution: def divideArray(self, nums: List[int], k: int) - List[List[int]]: max_num max(nums) count [0] * (max_num 1) for num in nums: count[num] 1 res [] group [] for num in range(max_num 1): while count[num] 0: group.append(num) count[num] - 1 if len(group) 3: if group[2] - group[0] k: return [] res.append(group) group [] return resJava使用定长group数组与下标i避免重复分配public class Solution { public int[][] divideArray(int[] nums, int k) { int max 0; for (int num : nums) { max Math.max(max, num); } int[] count new int[max 1]; for (int num : nums) { count[num]; } int[][] res new int[nums.length / 3][3]; int[] group new int[3]; int i 0; for (int num 0, idx 0; num max; num) { while (count[num] 0) { group[i] num; count[num]--; if (i 3) { if (group[2] - group[0] k) { return new int[][]{}; } for (int j 0; j 3; j) { res[idx][j] group[j]; } i 0; idx; } } } return res; } }Cclass Solution { public: vectorvectorint divideArray(vectorint nums, int k) { int maxNum *max_element(nums.begin(), nums.end()); vectorint count(maxNum 1, 0); for (int num : nums) { count[num]; } vectorvectorint res; vectorint group; for (int num 0; num maxNum; num) { while (count[num] 0) { group.push_back(num); count[num]--; if (group.size() 3) { if (group[2] - group[0] k) { return {}; } res.push_back(group); group.clear(); } } } return res; } };Go内层用for count[num] 0的无边界 for 循环连续消减同一数字的计数func divideArray(nums []int, k int) [][]int { maxNum : 0 for _, num : range nums { if num maxNum { maxNum num } } count : make([]int, maxNum1) for _, num : range nums { count[num] } res : [][]int{} group : []int{} for num : 0; num maxNum; num { for count[num] 0 { group append(group, num) count[num]-- if len(group) 3 { if group[2]-group[0] k { return [][]int{} } res append(res, group) group []int{} } } } return res }Kotlin / Swift / Rust / C# / JavaScript 的计数排序版本结构与上述一致核心均为“count[num]的 while 循环 组满 3 个即校验group[2] - group[0] k”其中 Rust 版对usize与i32做了显式类型转换count[num as usize]Swift 版用nums.max()!取最大值。完整的九种语言代码可直接查阅原文档 articles/divide-array-into-arrays-with-max-difference.md。时间/空间复杂度时间复杂度$O(n m)$空间复杂度$O(n m)$其中 $n$ 是nums的大小$m$ 是nums中的最大元素。这里有一个从实现细节中可以确认的适用边界方案二的count数组长度是max 1因此只有当 $m$最大值与 $n$ 同数量级或更小、且题目值域非负时才是真正“更快”的选择若数值稀疏例如最大值接近 $10^9$$O(m)$ 的内存会立刻不可行应退回方案一。这也解释了为什么该方案原文档标注的前提是“值域受限时”。两种方案对比与选型维度方案一比较排序 贪心方案二计数排序 贪心时间复杂度$O(n \log n)$$O(n m)$空间复杂度$O(n)$输出$O(n m)$输出 计数表关键前提无特殊前提值域有界且非负$m$ 不能远大于 $n$实现难度低几行核心代码中需维护 count 与 group 状态工程默认选择通用首选值域受限时如题目给出 $nums[i] \le 100$ 类约束从两方案的源码对照可以看出无论采用哪种排序分组校验逻辑完全相同——都是“凑满 3 个校验首尾差 k 即失败”。这说明排序方式只是性能优化维度算法正确性完全由贪心判定承担。常见错误与陷阱Common Pitfalls原文档用三个具体反例总结了最容易踩的坑全部保留如下。陷阱一检查错了差值的两个端点排序后的三元组中最大差值出现在第一个与第三个元素之间最小值与最大值而不是相邻元素之间。只检查相邻差会漏掉真正的约束# Wrong: Checking adjacent differences for i in range(0, len(nums), 3): if nums[i1] - nums[i] k or nums[i2] - nums[i1] k: return [] # Correct: Check first and third elements for i in range(0, len(nums), 3): if nums[i2] - nums[i] k: return []陷阱二忘记先排序贪心方法只在已排序数组上才成立。不排序时“连续的三个元素”在数值上未必接近即使存在合法解也会误判失败# Wrong: Missing sort def divideArray(nums, k): res [] for i in range(0, len(nums), 3): if nums[i2] - nums[i] k: # Not meaningful without sorting! return [] res.append(nums[i:i3]) return res # Correct: Sort first def divideArray(nums, k): nums.sort() # Critical step! res [] for i in range(0, len(nums), 3): if nums[i2] - nums[i] k: return [] res.append(nums[i:i3]) return res陷阱三失败时的返回值类型不对当不存在合法划分时应返回空的二维数组而不是None、null或“包含一个空子数组的二维数组”。返回类型本身是正确性的一部分// Wrong: Returning null if (nums[i 2] - nums[i] k) { return null; // Incorrect type! } // Wrong: Returning array with empty element return new int[][]{ {} }; // Correct: Return empty 2D array if (nums[i 2] - nums[i] k) { return new int[][]{}; }这一点与上文 Java 方案一/方案二实现中统一使用return new int[][]{};的写法互相印证。小结本文以仓库中的题解文档 articles/divide-array-into-arrays-with-max-difference.md 为骨架完整覆盖了两条实现路线排序 贪心$O(n \log n)$排序后以步长 3 分组仅需校验每组nums[i2] - nums[i] k是通用首选计数排序 贪心$O(n m)$值域受限时用频次表代替比较排序线性扫描完成分组但受最大值 $m$ 的内存上限约束。两条路线共享同一个贪心不变量排序后固定三连组即为最优划分任一组越界则无解三个陷阱校验端点选错、漏排序、返回值类型错误则是多语言实现时最容易失分的位置。仓库内同系列的分组题解 divide-array-into-equal-pairs.md 采用“排序 连续段分析”的思路可作为本题贪心思想的邻近练习对照阅读。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考