二倍数对数组Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。
示例 1：
输入：arr = [3,1,3,6]
输出：false
示例 2：
输入：arr = [2,1,2,6]
输出：false
示例 3：
输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
提示：
- 0 <= arr.length <= 3 * 104
- arr.length 是偶数
- -105 <= arr[i] <= 105
# 思路
HashMap
# 解法
class Solution {
public boolean canReorderDoubled(int[] arr) {
Arrays.sort(arr);
//if (arr[0] == arr[arr.length - 1] && arr[0] == 0) return true;
Map<Integer, Integer> map = new HashMap<>();
for (int i : arr) {
if (i < 0) {
if (map.containsKey(2 * i) && map.get(2 * i) != 0) {
map.put(2 * i, map.get(2 * i) - 1);
} else {
map.put(i, map.getOrDefault(i, 0) + 1);
}
} else {
if (map.containsKey(i) && map.get(i) != 0) {
map.put(i, map.get(i) - 1);
} else {
map.put(2 * i, map.getOrDefault(2 * i, 0) + 1);
}
}
}
for (int i : map.values()) {
if (i != 0) {
return false;
}
}
return true;
// -8 -4 -4 -2 1 1 2 2 4 8
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 总结
- 分析出几种情况，然后分别对各个情况实现
