Java O(N^2)|Pruning Same differences
We can see the range of the array is so small. The largest array length is just 1000. So we can guess the k by two different indices elements, and then use hash
We can see the range of the array is so small. The largest array length is just **1000**. So we can guess the **k** by two different indices elements, and then use hash map to check the answer is right or not.\nSpecifically, the smallest element must be in the lower array,if it in the higher array,  we can not find the smaller one put in the lower. If the second element is the same as previous, it means it must not be the right answer, because we checked the previous by same value.\nAnother noteworthy thing is the **k** is positive, so we cannot assign **k** to **0**.\n\n``` java\nclass Solution {\n    public int[] recoverArray(int[] nums) {\n        Arrays.sort(nums);\n        int n = nums.length;\n        // the first index element, must be one of the lower elements,so we just need to calculate all the difference between the first element with other\n        for(int i = 1; i < n; i++){\n            //If the seond element is the same as the previous, don\'t check it\n            if(i>1&&nums[i]==nums[i-1])\n                continue;\n\n            int diff = nums[i]-nums[0];\n            //If the difference between two elements is odd, it means we cannot find the answer here\n            //k cannot be zero\n            if(diff%2!=0 || diff == 0)\n                continue;\n            int[] tmp = findOriginalArray(nums,diff/2);\n            if(tmp.length>0)\n                return tmp;\n        }\n        return nums;\n    }\n\n    public int[] findOriginalArray(int[] changed,int t) {\n        int n = changed.length;\n        if(n%2!=0)\n            return new int[0];\n\n        int[] ans = new int[n/2];\n        int i = 0;\n        Map<Integer,Integer> map = new HashMap<>();\n        for(int item:changed){\n            //if we find the smaller elements saved ever before,delete it\n            //otherwise, save it in the hash map\n            if(!map.containsKey(item-2*t)){\n                map.putIfAbsent(item,0);\n                map.put(item,map.get(item)+1);\n            }else if(map.get(item-2*t)==1){\n                map.remove(item-2*t);\n                ans[i++]=item-t;\n            }else{\n                map.put(item-2*t,map.get(item-2*t)-1);\n                ans[i++]=item-t;\n            }\n        }\n\n        return i==n/2&&map.isEmpty()?ans:new int[0];\n    }\n}\n```\n
['Java']