给定一个长度为偶数的整数数组 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

这是一道很有意思的题，也是值得做的题。看题很难理解，但是我们只要从[0, len(arr) / 2]代入公式循环一遍，就知道需要做什么。其实这道题要求的是给一个数组，判断其能否被分成长度为len(arr) / 2的两个数组，其中前一个数组每一个元素能与后一个数组中的一个元素形成一一对应关系，并且关系是两倍。

看到这里，就会想到要计数，看到计数就用map。我们首先遍历数组将所有数的出现次数统计，然后判断0的次数，因为如果要满足条件，0肯定是成对出现的，因为0*2=0，所以要么0不出现，要么出现次数是偶数；对于剩下的数，比如一个数i，要么它满足它是i/2这个数两倍，要么它满足对应i*2这个数，从这里可以推断，一个数i，它的出现次数肯定是大于等于i/2这个数的出现次数，即得到cnt.get(2 * i) >= cnt.get(i)。

我们用一个list存储所有出现过的数，并且按照绝对值大小排序，因为一个数不管正负，乘以2都不影响。每一次判读过后，都需要更新i*2的个数。

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        // 记录每个数字出现次数
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i : arr) {
            cnt.put(i, cnt.getOrDefault(i, 0) + 1);
        }
        // 判断0的次数
        if (cnt.getOrDefault(0, 0) % 2 != 0) return false;

        // 将值全变为正数后升序排序
        List<Integer> list = new ArrayList<>();
        for (int i : cnt.keySet()) {
            list.add(i);
        }
        list.sort((a, b) -> Math.abs(a) - Math.abs(b));

        for (int i : list) {
            // 2*i的出现次数一定大于等于i的出现次数
            if (cnt.getOrDefault(2 * i, 0) < cnt.get(i)) return false;
            // 维护2*i的出现次数
            cnt.put(2 * i, cnt.getOrDefault(2 * i, 0) - cnt.get(i));
        }

        return true;
    }
}

结果如下：