rust 13ms simple solution with explain
\n\n\n# Intuition\nSort the array. For the first item and any other item, their differenca can be a $2k$. For every possible $k$, verify the nums weather this $
![image.png](https://assets.leetcode.com/users/images/e8bbade6-8178-4e9a-8104-bb1983da3a02_1715280438.8859682.png)\n\n\n# Intuition\nSort the array. For the first item and any other item, their differenca can be a $2k$. For every possible $k$, verify the nums weather this $k$ can recover the array.\n\nSince the array is sorted, the programm will always meet the $arr[i]-k$ before $arr[i]+k$. So you can assume if you meet some number not registered, it adds $k$ is an element in the array. Then register it adds $2*k$ and expect you may meet it in the future. After the scan, there are no any number registered to be met, it is valid.\n\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nuse std::collections::VecDeque;\n\nimpl Solution {\n    pub fn recover_array(nums: Vec<i32>) -> Vec<i32> {\n        let mut nums=nums.clone();\n        nums.sort_unstable();\n        for i in 1..nums.len(){\n            if (nums[i]-nums[0])%2!=0||nums[i]==nums[0]{continue;}\n            let k=(nums[i]-nums[0])/2;\n            match Self::velify(&nums, k){\n                Some(res)=>{return res;}\n                None=>()\n            }\n        }\n        Vec::new()\n    }\n\n    fn velify(nums: &Vec<i32>, k: i32)->Option<Vec<i32>>{\n        let mut res=Vec::new();\n        let mut to_match=VecDeque::new();\n        for &i in nums{\n            if to_match.len()==0||to_match[0]!=i{\n                to_match.push_back(i+k*2);\n                res.push(i+k);\n            }else{\n                to_match.pop_front();\n            }\n            // early return to save time\n            if res.len()>nums.len()/2{return None;}\n        }\n        // theoretically every invalid array will cause early return\n        // the else branch will never be select\n        if to_match.len()==0{Some(res)}else{None}\n    }\n}\n\n```
['Rust']