2018-09-12 888. Fair Candy Swap

题意：给你两个数组，从两个数组中各选一个数交换位置，新得到的两个数组的元素总和相等。
思路一：先得到两个数组各自的元素总和，进而得到平均值，再遍历元素少的vector，得到每个元素如果交换的话需要从另一个vector中得到什么值，查找另一个vector中是否有该值，如果有即是答案（关键是查找，使用二分查找（logN））。
思路二：查找之前的步骤与思路一样，在查找的时候，使用bool数组存储另一个vector中有哪些数，直接通过数组下标访问（比二分更快，时间复杂度O(1)）。

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        vector<int> *small, *big;
        int flg = 0;
        if(A.size() < B.size()){
            small = &A;
            big = &B;
        }else{
            flg = 1;
            small = &B;
            big = &A;
        }
        int smallv = 0, bigv = 0;
        for(auto item : *small)
            smallv += item;
        bool bigflg[100005] = {0};
        for(auto item : *big){
            bigv += item;
            bigflg[item] = 1;
        }
        int target = (bigv - smallv) / 2;
        for(auto item : *small){
            int findNum = item + target;
            if(findNum > 0 && findNum <= 100000 && bigflg[findNum]){
                if(flg == 0)
                    return {item, findNum};
                return {findNum, item};
            }
        }
    }
};

static int x = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

注意：在一个vector中查找某元素是否存在的最快速度不是二分查找，也不需要把这些元素都放到set集合中，而是将这个vector对应的值转化成一个bool数组，直接根据下标访问。