2007. Find Original Array From Doubled Array
题目：给定一个阵列，若该阵列可以由某个阵列的所有元素乘2之后组合成，我们
说这个阵列是一个 Doubled Array，找出这个阵列是否是 Doubled Array 若存在则
返回该阵列变成 Doubled Arraay前的阵列。
Example:
[1,3,4] => [1,3,4,2,6,8]
思路：
1.先排序整个阵列让每次遍历时都从最小开始拿，避免：[2, 4, 2, 1] 这种 Case
会 2 -> 2 且 4 -> 1。
2.统计 Doubled Array 内的所有元素个数储存在HashMap。
3.遍历Double dArray的每个元素，若HashMap存在该元素则该元素和两倍的该元素数量
减一，把该元素储存在 List 中。
4.检查HashMap所有元素的数量，若全为0表示每个元素都相互匹配，将List转为int[]
返回，若任意元素不为0表示不匹配，返回空的int[]。
Java Code：
class Solution {
public int[] findOriginalArray(int[] nums) {
int n = nums.length;
if(n % 2 == 1) return new int[0];
Arrays.sort(nums);
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums)
map.put(num ,map.getOrDefault(num,0) + 1);
List<Integer> list = new ArrayList<>();
for (int num : nums) {
int doubleChanged = num * 2;
if (map.containsKey(doubleChanged) && map.get(num) > 0) {
list.add(num);
map.put(num, map.get(num) - 1);
map.put(doubleChanged, map.get(doubleChanged) - 1);
}
}
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() != 0)
return new int[0];
}
int[] res = new int[list.size()];
int i = 0;
for(int num : list)
res[i++] = num;
return res;
}
}