2022-04-27：Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：
对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k
不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 lower 和 higher 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。
给你一个由 2n 个整数组成的整数数组 nums ，其中 恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回 原数组 arr 。如果出现答案不唯一的情况，返回 任一 有效数组。
注意：生成的测试用例保证存在 至少一个 有效数组 arr 。
输入：nums = [2,10,6,4,8,12]
输出：[3,7,11]
解释：
如果 arr = [3,7,11] 且 k = 1 ，那么 lower = [2,6,10] 且 higher = [4,8,12] 。
组合 lower 和 higher 得到 [2,6,10,4,8,12] ，这是 nums 的一个排列。
另一个有效的数组是 arr = [5,7,9] 且 k = 3 。在这种情况下，lower = [2,4,6] 且 higher = [8,10,12] 。
力扣2122. 还原原数组。
来自小米。
答案2022-04-27：
先排序。大数的第1个数需要循环。
时间复杂度：O(N**2)。
代码用rust编写。代码如下：
fn main() { let mut nums: Vec<isize> = vec![2, 10, 6, 4, 8, 12]; let ans: Vec<isize> = recover_array(&mut nums); println!("ans = {:?}", ans);}fn recover_array(nums: &mut Vec<isize>) -> Vec<isize> { nums.sort_by(|a, b| a.cmp(&b)); let n = nums.len() as isize; // nums[0] -> 小数组的第0个 let m = n >> 1; // 谁是大数组的第0个？不知道，试！first位置的数！ for first in 1..=m { // d = 2 * k; k正数！ let d = nums[first as usize] - nums[0]; if d > 0 && (d & 1) == 0 { // 试图生成原始数组！ans！ let mut ans: Vec<isize> = vec![]; for _k in 0..m { ans.push(0); } let mut i: isize = 0; let mut set: Vec<bool> = vec![]; for _k in 0..n { set.push(false); } let k: isize = d >> 1; let mut l: isize = 0; let mut r: isize = first; while r < n { while set[l as usize] { l += 1; } if l == r { r += 1; } else if nums[r as usize] - nums[l as usize] > d { break; } else if nums[r as usize] - nums[l as usize] < d { r += 1; } else { set[r as usize] = true; r += 1; ans[i as usize] = nums[l as usize] + k; l += 1; i += 1; } } if i == m { return ans; } } } return vec![];}
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_02_2_week/Code05_RecoverTheOriginalArray.java)