My Solutions
1. Use the std::unordered_map2. Don't use the std::unordered_map
**1. Use the `std::unordered_map`**
```
/**
 * Time Complexity: O(n * n)
 * Space Complexity: O(n)
 * where `n` is the length of the vector `nums`
 */
class Solution {
 public:
  vector<int> recoverArray(vector<int> &nums) {
    const int n = static_cast<int>(nums.size()) >> 1;
    sort(nums.begin(), nums.end());
    unordered_map<int, int> num_to_count;
    for (const int num : nums) {
      ++num_to_count[num];
    }
    
    vector<int> ret;
    for (int i = 1; i < n + 1; ++i) {
      const int twice_k = nums[i] - nums.front();
      if (twice_k > 0 && twice_k % 2 == 0 && valid(nums, num_to_count, twice_k, ret)) {
        return ret;
      }
    }
    throw "impossible path";
  }
  
 private:
  bool valid(const vector<int> &nums, unordered_map<int, int> num_to_count, const int twice_k, vector<int> &result) {
    for (const int lower : nums) {
      auto itr_lower = num_to_count.find(lower);
      if (itr_lower == num_to_count.end()) {
        continue;
      }

      const int lower_count = itr_lower->second;
      const int higher = lower + twice_k;
      auto itr_higher = num_to_count.find(higher);
      if (itr_higher == num_to_count.end() || itr_higher->second < lower_count) {
        result.clear();
        return false;
      }
      
      for (int i = 0; i < lower_count; ++i) {
        result.emplace_back((lower + higher) >> 1);
      }
      num_to_count.erase(itr_lower);
      if ((itr_higher->second -= lower_count) == 0) {
        num_to_count.erase(itr_higher);
      }
    }
    return true;
  }
};
```
**2. Don't use the `std::unordered_map`**
```
/**
 * Time Complexity: O(n * n)
 * Space Complexity: O(n)
 * where `n` is the length of the vector `nums`
 */
class Solution {
 public:
  vector<int> recoverArray(vector<int> &nums) {
    const int n = static_cast<int>(nums.size()) >> 1;
    sort(nums.begin(), nums.end());
    vector<int> ret;
    for (int i = 1; i < n + 1; ++i) {
      const int twice_k = nums[i] - nums.front();
      if (twice_k > 0 && (twice_k & 1) == 0) {
        ret.clear();
        bool visited[n << 1];
        memset(visited, 0, sizeof(visited));
        int i_lower = 0;
        int i_higher = i;
        while (ret.size() < n &&
               i_higher < (n << 1) &&
               nums[i_higher] - nums[i_lower] == twice_k) {
          visited[i_lower] = true;
          visited[i_higher] = true;
          ret.emplace_back(nums[i_lower] + (twice_k >> 1));
          for (; i_lower < (n << 1) && visited[i_lower]; ++i_lower) {
          }
          for (;
               i_higher < (n << 1) && (visited[i_higher] || nums[i_higher] < nums[i_lower] + twice_k);
               ++i_higher) {
          }
        }
        if (ret.size() == n) {
          return ret;
        }
      }
    }
    throw "impossible path";
  }
};
```
['C++']