888. Fair Candy Swap

问题：

数组A，和数组B，求交换两数组任意一个元素，使得两数组和相等。

返回{A交换出的元素，B交换出的元素}

Example 1:
Input: A = [1,1], B = [2,2]
Output: [1,2]

Example 2:
Input: A = [1,2], B = [2,3]
Output: [1,2]

Example 3:
Input: A = [2], B = [1,3]
Output: [2,3]

Example 4:
Input: A = [1,2,5], B = [2,4]
Output: [5,4]

　　

解法：

求出A和B的元素和SumA和SumB

他们所要拿出交换的元素之差，即是 各自总和 与 平均数（SumA+SumB）/2的差值diff

那么，对A的各个元素itemA，去+diff，是否存在在B中，如果存在，则交换{itemA, itemA+diff}

这里我们要在B中查找任意元素是否存在，则考虑使用unordered_map，则有：

代码参考：

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        int sumAll=0;
        int sumA=0, sumB=0;
        unordered_map<int,int>Bmap;
        vector<int> res(2,0);
        for(int itemA:A){
            sumAll+=itemA;
            sumA+=itemA;
        }
        for(int itemB:B){
            sumAll+=itemB;
            sumB+=itemB;
            Bmap[itemB]++;
        }
        int diff=sumAll/2-sumA;
        for(int itemA:A){
            auto it=Bmap.find(itemA+diff);
            if(it!=Bmap.end()){
                res={itemA, it->first};
                break;
            }
        }
        return res;
    }
};

♻️优化：引入bitset类型变量：代表一个二进制数。

第n位，为0或者1，那么我们可以用它来替换unodered_map，

若存在itemB，那么bitset[itemB]=1，否则为0：具体实现方法：bitset.set(itemB);

查看是否存在这样的itemB，则有方法：bitset.test(itemB); 若存在（itemB位为1）返回true，否则返回false。

代码参考：

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        int sumA=0, sumB=0;
        bitset<100001>Bmap;//100001位二进制数位
        for(int itemA:A){
            sumA+=itemA;
        }
        for(int itemB:B){
            sumB+=itemB;
            Bmap.set(itemB);
        }
        int diff=(sumA+sumB)/2-sumA;
        for(int itemA:A){
            int it=itemA+diff;
            if(it>=1 && it<=100000 && Bmap.test(it)==true){
                return {itemA, it};
            }
        }
        return {-1,-1};
    }
};