leetcode二倍数对数组 -- Map

给定一个长度为偶数的整数数组 A，只有对 A 进行重组后可以满足 “对于每个 0 <= i < len(A) / 2，都有 A[2 * i + 1] = 2 * A[2 * i]” 时，返回 true；否则，返回 false。

示例1

输入：[3,1,3,6]
输出：false

示例2

输入：[2,1,2,6]
输出：false

示例3

输入：[4,-2,2,-4]
输出：true
解释：我们可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

示例4

输入：[1,2,4,16,8,4]
输出：false

提示：

• 0 <= A.length <= 30000
• A.length 为偶数
• -100000 <= A[i] <= 100000

刚刚学会了map,发现这道题也可以使用map。这题由于是求二倍数对数组，因此必须从小到大进行遍历，否则考虑数组[2,4,1,8]，如果2先与4进行配对了，1和8无法配对，需要从1开始配对，才能得出正确结果。这题还要考虑负数的问题。为了简化问题，我先将自然数与负数分成两个数组，再进行求解。为了简化代码，在存储负数的数组时，我将其取了绝对值。

class Solution {
public:
    bool findPair(vector<int> A){
        map<int,int> pairMap;
        for(int i=A.size()-1;i>=0;i--){
            int pairA = A[i] * 2;
            auto iter = pairMap.find(pairA);
            if(iter != pairMap.end() && iter->second != 0){
               iter->second -= 1;
            }
            else{
                auto iterA = pairMap.find(A[i]);
                if(iterA != pairMap.end()){
                    iterA->second += 1;
                }
                else{
                    pairMap.insert(pair<int,int>(A[i],1));
                }
            }
        }
        for(auto iter=pairMap.begin();iter!=pairMap.end();iter++){
            if(iter->second !=0) return false;
        }
        return true;
    }
    bool canReorderDoubled(vector<int>& A) {
        vector<int> plusA;
        vector<int> minusA;
        for(int i=0;i<A.size();i++){
            if(A[i]>=0) plusA.push_back(A[i]);
            else minusA.push_back(abs(A[i]));
        }
        sort(plusA.begin(),plusA.end());
        sort(minusA.begin(),minusA.end());
        return findPair(plusA) && findPair(minusA);
    }
};

题目链接：https://leetcode-cn.com/contest/weekly-contest-114/problems/array-of-doubled-pairs/