本文涉及知识点

C++算法：滑动窗口及双指针总结

LeetCode2122. 还原原数组

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 。
示例 1：
输入：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] 。
示例 2：
输入：nums = [1,1,3,3]
输出：[2,2]
解释：
如果 arr = [2,2] 且 k = 1 ，那么 lower = [1,1] 且 higher = [3,3] 。
组合 lower 和 higher 得到 [1,1,3,3] ，这是 nums 的一个排列。
注意，数组不能是 [1,3] ，因为在这种情况下，获得 [1,1,3,3] 唯一可行的方案是 k = 0 。
这种方案是无效的，k 必须是一个正整数。
示例 3：
输入：nums = [5,435]
输出：[220]
解释：
唯一可行的组合是 arr = [220] 且 k = 215 。在这种情况下，lower = [5] 且 higher = [435] 。
提示：
2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 10⁹
生成的测试用例保证存在 至少一个 有效数组 arr

暴力解法

nums最大值iMax，必定是原始数组中最大值，删除iMax和iMax-2$\times$k。
不断重复此过程。数组查找和删除都是O(n)，故总时间复杂度是：O(nn)。
如果用多键集合，查找和删除都是O(logn)，总时间复杂度是：O(nlogn)。
由于要枚举k，所以总时间复杂度需要乘以O(n)。

滑动窗口

对nums排序，并不删除nums[i]而是置为-1。
j指向当前iMax+k，i指向当前iMax-k。显然i,j都是减少。共处理nums.size()/2次。
注意：nums[j-2*k] 为-1是非法，需要排除。

代码

核心代码

class Solution {
		public:
			vector<int> recoverArray(vector<int>& nums) {
				const int N = nums.size();				
				sort(nums.begin(), nums.end());
				auto Do = [&](vector<int> nums, int k)
				{
					vector<int> ans;
					int i = N - 1, j = N - 1;
					for (int m = N / 2; m > 0; m--) {
						while (-1 == nums[j]) { j--; };
						while ((i >= 0 )&&( nums[j] - 2 * k != nums[i])) { i--; }
						if ((i < 0)||(nums[i] <= 0 )) { return ans; }
						ans.emplace_back(nums[j]-k);
						nums[i] = nums[j] = -1;
					}
					return ans;
				};
				for (int i = 0; i < N; i++) {
					const int sub = nums.back() - nums[i];
					if (sub && (0 == sub % 2))
					{
						auto ans = Do(nums, sub / 2);
						if (ans.size() * 2 == N) { 
							return ans; }
					}
				}
				return {};
			}
		};