Check common possible k from both sides[Java][8ms][100%]
Idea\nIf we sort nums, then nums[0] must be is the lower value of the smallest value of the original array(min(arr) - k).\nThen, we can check the differences nu
**Idea**\nIf we sort `nums`, then `nums[0]` must be is the `lower` value of the smallest value of the original array(`min(arr) - k`).\nThen, we can check the differences `nums[i] - nums[0]`  for the one that matches all pairs. The differences to consider must be positive and even.\n\n**Optimizations**\n1. We can check only the differences  `nums[i] - nums[0]` for  `1 <= i < n`, since nums[n] is the rightmost possible match for `nums[0]`.\n2. Similarly to `nums[0]` being the `lower` value of the smallest number in te original array, `nums[2n - 1]` must be the `higher` value of the largest number in the original array(`max(arr) + k`). So we can also find the (positive and even) differences `nums[2n - 1] - nums[i]` (`2n - 1 - n <= i < 2n`) and check only the ones that appear also in the differences found from `nums[i] - nums[0]`.\n\n**Complexity**\nTime: O(n^2)\nSpace: O(n)\n\n**Code**\n```\nclass Solution {\n    public int[] recoverArray(int[] nums) {\n        int n2 = nums.length;\n        int n = n2 / 2;\n        int[] arr = new int[n];\n        \n        Arrays.sort(nums);\n        // find valid differences: nums[i] - nums[0]\n        Set<Integer> diffs1 = new HashSet<>();\n        for (int i = 1; i <= n; i++) {\n            int cand = nums[i] - nums[0];\n            if (cand > 0 && (cand & 1) == 0) {\n                diffs1.add(cand);\n            }\n        }\n        \n        // find valid differences: nums[2n - 1] - nums[i] that also appear in the nums[i] - nums[0] differences\n\t\t// \n        Set<Integer> diffs2 = new HashSet<>();\n        for (int i = n2 - n - 1; i < n2 - 1; i++) {\n            int cand = nums[n2 - 1] - nums[i];\n            if (cand > 0 && (cand & 1) == 0 && diffs1.contains(cand)) {\n                diffs2.add(cand);\n            }\n        }\n        \n        // check each candidate difference\n        outer:\n        for (int diff : diffs2) {\n            Deque<Integer> dq = new ArrayDeque<>();\n            int p = 0;\n            int k = diff / 2;\n            for (int num : nums) {\n                if (!dq.isEmpty() && num == dq.peekFirst()) {\n                    dq.pollFirst();\n                    continue;\n                } else {\n                    if (p == n) continue outer;\n                    arr[p++] = num + k;\n                    dq.addLast(num + diff);\n                }\n                \n            }\n            if (p == n) break;\n        }\n        \n        return arr;\n    }\n    \n}\n```
['Greedy', 'Java']