JAVA |  HashMap trying all possible k
After sorting, k can be (nums[i]-nums[0])/2 for any i in 1 ~ n, then use a HashMap to check if such k is valid.\n\n\nclass Solution {\n    Map<Integer, Integer>
After sorting, k can be (nums[i]-nums[0])/2 for any i in 1 ~ n, then use a HashMap<element, count> to check if such k is valid.\n\n```\nclass Solution {\n    Map<Integer, Integer> countMap;\n    public int[] recoverArray(int[] nums) {\n        int n = nums.length/2;\n        Arrays.sort(nums);\n        countMap = new HashMap<>();\n        for(int i=0; i<nums.length; i++) {\n            countMap.put(nums[i], countMap.getOrDefault(nums[i], 0) + 1);\n        }\n\n        for(int i=1; i<=n; i++) {\n            int k = (nums[i]-nums[0])/2;\n            if(k == 0) continue; // k is positive\n            int[] ret = helper(nums, k);\n            if(ret != null) {\n                return ret;\n            }\n        }\n\n        return null;\n    }\n    \n    int[] helper(int[] nums, int k) { // check if k is valid and generate return array\n        Map<Integer, Integer> map = new HashMap<>(countMap);\n        List<Integer> list = new ArrayList<>();\n        for(int i:nums) {\n            if(!map.containsKey(i)) continue;\n            int counterPart = i + 2*k;\n            if(!map.containsKey(counterPart)) return null;\n            list.add(i+k);\n            \n            map.put(i, map.get(i) - 1);\n            if(map.get(i) == 0) map.remove(i);\n            map.put(counterPart, map.get(counterPart) - 1);\n            if(map.get(counterPart) == 0) map.remove(counterPart);\n        }\n        int[] ret = new int[list.size()];\n        for(int j=0; j<list.size(); j++) {\n            ret[j] = list.get(j);\n        }\n        return ret;\n    }\n} \n```
[]