2122 还原原数组（枚举，双指针）

2122 还原原数组（枚举，双指针）

1. 问题描述：

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 ^ 9
生成的测试用例保证存在至少一个有效数组 arr

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-the-original-array/

2. 思路分析：

为了方便处理数组中的元素可以先排序，分析题目可以知道nums[0] + k肯定属于lower中的元素，而且low与higher中的元素是一一对应的，所以我们可以从下标为1的位置开始枚举与之匹配的元素higher[i]，并且与low[0]匹配的higher[i]的奇偶性肯定是一样的，此时的k = (higher[i] - low[0]) // 2才是一个整数，当我们找到当前与nums[0]匹配的元素之后，可以使用一个循环找到下一组匹配的low[l]与higher[r]，因为数组是从小到大进行排序的所以可以使用双指针来寻找（满足单调性），并且在找到对应的匹配之后将nums[l] + k加入到答案中，如果循环结束那么答案的长度为n // 2说明当前的已经找到了符合要求的答案，返回对应的答案即可，如果没有找到那么枚举下一个与nums[0]匹配的元素知道找到答案就结束了。

3. 代码如下：

from typing import List


class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 从小到大排序
        nums.sort()
        for i in range(1, n):
            # nums[i]与nums[0]的奇偶性相同, 枚举当前的nums[i]作为nums[0]匹配的元素
            if nums[i] == nums[0] or (nums[i] - nums[0]) % 2 == 1: continue
            used = [0] * n
            # 标记已经被使用了, 找到了当前与0匹配的另外一个数字
            used[0] = used[i] = 1
            k = (nums[i] - nums[0]) // 2
            # res是原数组
            res = [nums[0] + k]
            # 双指针
            l, r = 0, i
            for j in range(1, n // 2):
                while used[l] == 1: l += 1
                # 寻找与左边l匹配的位置r
                while r < n and (used[r] == 1 or nums[r] - nums[l] != 2 * k): r += 1
                if r >= n: break
                res.append(nums[l] + k)
                # 标记已经被使用了
                used[l] = used[r] = 1
            if len(res) == n // 2: return res
        return None