目标
给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。
将这个数组划分为 n / 3 个长度为 3 的子数组，并满足以下条件：
- 子数组中 任意 两个元素的差必须 小于或等于 k 。
返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。
示例 1：
输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
输出：[[1,1,3],[3,4,5],[7,8,9]]
解释：
每个数组中任何两个元素之间的差小于或等于 2。
示例 2：
输入：nums = [2,4,2,2,5,2], k = 2
输出：[]
解释：
将 nums 划分为 2 个长度为 3 的数组的不同方式有：
[[2,2,2],[2,4,5]] （及其排列）
[[2,2,4],[2,2,5]] （及其排列）
因为有四个 2，所以无论我们如何划分，都会有一个包含元素 2 和 5 的数组。因为 5 - 2 = 3 > k，条件无法被满足，所以没有合法的划分。
示例 3：
输入：nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14
输出：[[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]]
解释：
每个数组中任何两个元素之间的差小于或等于 14。
说明：
- n == nums.length
- 1 <= n <= 10^5
- n 是 3 的倍数
- 1 <= nums[i] <= 10^5
- 1 <= k <= 10^5
思路
将数组划分为 n / 3 个长度为 3 的数组，使得子数组内元素的差值不超过 k。如果有多个答案返回任意一个即可，如果满足条件的子数组不够 n / 3，返回空数组。
注意将原数组划分为 n / 3 个数组，先从数组中取 3 个元素，再从剩余元素中取 3 个 …… 。并不是取不重复的长度为 3 的子数组。
排序后每三个元素一组判断即可，因为相邻元素的差值最小，只要有一组不满足条件，那么个数就不够，直接返回空数组。
代码
/**
* @date 2025-06-18 0:08
*/
public class DivideArray2966 {
public int[][] divideArray(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int[][] res = new int[n / 3][];
for (int i = 1; i < n - 1; i += 3) {
int cur = nums[i];
int prev = nums[i - 1];
int next = nums[i + 1];
if (next - prev > k) {
return new int[][]{};
}
res[i / 3] = new int[]{prev, cur, next};
}
return res;
}
}
性能
