[100%] [50ms]  WITHOUT map
First sort the nums array,  nums[0] belong to low array. \nTry every possible diff in array, and diff must be even. k = diff / 2;\nEach element in low array (v)
First sort the nums array,  nums[0] belong to low array. \nTry every possible diff in array, and diff must be even. k = diff / 2;\nEach element in low array (v) should have its equivalent in  high arrray (v + k + k). \nMaintain a pointer for the last element in low array that haven\'t found its equalient in high array yet, \n1 If pointer is valid and next element\'s value is pointer\'s value + k + k, then next element is the in high array. pointer++;\n2 Otherwise next element is in low array.\n\n```\nclass Solution {\npublic:\n    int n;\n    vector<int> recoverArray(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        int n2 = nums.size();\n        n = n2/2;\n        int a = nums[0];\n        vector<int> v1, v2, ans;\n        v1.reserve(n);v2.reserve(n);\n        for (int i = 1; i < n2; i++)\n        {\n            int k = nums[i] - a;\n            if (k % 2 == 1 || k == 0 || nums[i] == nums[i - 1]) continue;       \n            v1.clear();v2.clear();\n            v1.push_back(a);\n            int x = 0;\n            for (int j = 1; j < n2; j++)\n            {\n                if (x < v1.size() && (nums[j] == v1[x] + k)) {\n                    v2.push_back(nums[j]);\n                    x++;\n                } else  v1.push_back(nums[j]);\n            \n                if (v1.size() > n || v2.size() > n) break;\n            }\n            if (v1.size() != n || v2.size() != n) continue;\n            for (int i = 0; i < n; i++) ans.push_back((v1[i] + v2[i]) / 2);\n            return ans;\n        }\n        return ans; \n    }\n};\n```
['Greedy', 'C']