1
class Solution {
2
  public int[] recoverArray(int[] nums) {
3
    int N = nums.length;
4
    Arrays.sort(nums);
5
    List<Integer> diffList = new ArrayList<>();
6
    for (int i = 1; i < N; i++) {
7
      int diff = Math.abs(nums[i] - nums[0]);
8
      if (diff % 2 == 0 && diff > 0) diffList.add(diff / 2);
9
    }
10
    Map<Integer, Integer> map1 = new HashMap<>();
11
    for (int i = 0; i < N; i++) map1.put(nums[i], map1.getOrDefault(nums[i], 0) + 1);
12
    for (int diff : diffList) {
13
      Map<Integer, Integer> map = new HashMap<>(map1);
14
      List<Integer> tmp = new ArrayList<>();
15
      for (int i = 0; i < N; i++) {
16
        if (tmp.size() == N / 2) break;
17
        int low = nums[i];
18
        int high = low + 2 * diff;
19
        if (map.containsKey(low) && map.containsKey(high)) {
20
          tmp.add(low + diff);
21
          map.put(low, map.get(low) - 1);
22
          map.put(high, map.get(high) - 1);
23
          if (map.get(low) == 0) map.remove(low);
24
          if (map.get(high) == 0) map.remove(high);
25
        }
26
      }
27
      if (tmp.size() == N / 2) return tmp.stream().mapToInt(i -> i).toArray();
28
    }
29
    return null;
30
  }
31
}