千问 LeetCode 2122.还原原数组 public int[] recoverArray(int[] nums)

这道题的核心思路是枚举 + 双指针验证。

🧠 解题思路

1. 排序：首先将 nums 数组排序。排序后，最小的元素 nums[0] 必然是原数组某个元素减去 k 得到的（即 lower 数组中的最小值）。
2. 枚举 k：我们遍历排序后的数组，假设 nums[i] (i > 0) 是与 nums[0] 配对的 higher 值。
* 根据定义，higher - lower = 2k，所以 2k = nums[i] - nums[0]。
* 由于 k 必须是正整数，所以 2k 必须是大于 0 的偶数。如果差值是奇数或 0，则跳过。
3. 验证 k：对于每一个可能的 k，我们使用双指针或贪心策略来验证是否能将数组完全配对。
* 每次从未使用的数字中取出最小的一个作为 lower 值。
* 查找是否存在对应的 higher 值（即 lower + 2k）。
* 如果存在，则找到一对，将原数组元素 lower + k 加入结果，并标记这两个数为已使用。
* 如果不存在，说明当前的 k 不合法。
4. 返回结果：一旦找到合法的 k 并成功配对了所有数字，即可返回结果。

💻 Java 代码实现

import java.util.Arrays;

class Solution {
public int[] recoverArray(int[] nums) {
// 1. 排序，方便后续处理
Arrays.sort(nums);
int n = nums.length;

// 2. 枚举可能的 k
// nums[0] 一定是 lower 中的最小值
// 我们枚举 nums[i] 作为与 nums[0] 配对的 higher 值
for (int i = 1; i < n; i++) {
// 优化：如果当前数字和前一个数字相同，跳过，避免重复计算
if (nums[i] == nums[i - 1]) continue;

// 计算 2k
int diff = nums[i] - nums[0];

// k 必须是正整数，所以 2k 必须是正偶数
if (diff <= 0 || diff % 2 != 0) continue;

int k = diff / 2;

// 3. 尝试用当前的 k 还原数组
int[] result = tryRecover(nums, k);
if (result != null) {
return result;
}
}

return new int[0]; // 理论上不会执行到这里，因为题目保证有解
}

private int[] tryRecover(int[] nums, int k) {
int n = nums.length;
boolean[] used = new boolean[n]; // 标记数组，记录元素是否已被使用
int[] result = new int[n / 2];
int resultIdx = 0;

// 使用双指针贪心匹配
// 每次找未使用的最小值作为 lower，然后找对应的 higher
for (int i = 0; i < n; i++) {
if (used[i]) continue; // 如果当前数已使用，跳过

int lower = nums[i];
int higher = lower + 2 * k; // 对应的 higher 值

// 寻找 higher
boolean found = false;
for (int j = i + 1; j < n; j++) {
if (!used[j] && nums[j] == higher) {
// 找到配对
used[i] = true;
used[j] = true;
result[resultIdx++] = lower + k; // 原数组元素是 (lower + higher) / 2
found = true;
break;
}
}

// 如果找不到配对的 higher，说明当前 k 不合法
if (!found) {
return null;
}
}

return result;
}
}

📝 复杂度分析

* 时间复杂度：O(n² log n) 或 O(n²)。
* 排序需要 O(n log n)。
* 外层循环最多执行 O(n) 次。
* 内层 tryRecover 函数在最坏情况下需要 O(n²) 的时间（对于每个未使用的元素，都要向后查找配对）。
* 总体时间复杂度为 O(n log n + n³)，但在实际运行中，由于一旦找到合法的 k 就会立即返回，所以通常会更快。更精确的分析是 O(n²)，因为内层循环的总操作次数是线性的。
* 空间复杂度：O(n)，主要用于 used 数组和排序的栈空间。