题目描述

Alice和Bob有很多不同大小的糖果块，A[i]是Alice的第i个糖果块的大小，B[j]是Bob的第j个糖果块的大小。由于他们是好朋友，所以他们希望通过交换糖果块使得他们的糖果总量是一样的（糖果总量就是每个人拥有的糖果块大小的和）。

返回一个整数数组ans，ans[0]表示Alice交换的糖果块大小，ans[1]表示Bob交换的糖果块大小，可能有多个答案，返回任意一个合法答案即可，保证一定有答案。

样例

输入: A = [1,2,5], B = [2,4]
输出: [5,4]
说明：交换之后，Alice的糖果是[1,2,4], Bob的糖果是[2,5]，于是他们的糖果总和相等。

算法1

(哈希) $O(n)$

考虑交换A[i]和B[j]，则交换后两个数组的和的差会改变2*(A[i]-B[j])，因此要使得交换一次后两个数组的总和相等，则先求出两个数组的总和的差，然后再去找A和B数组看是否存在满足条件的两个数即可。对于B中每个数字B[j]，查找A中是否有A[i]-B[j]=t(t=(sumA-sumB)/2)，用哈希表使得A中的查找复杂度为O(1)。

时间复杂度分析：$O(n)$

C++ 代码

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        unordered_set<int> S(A.begin(), A.end());
        int sum1 = 0, sum2 = 0;
        for(int i = 0;i<A.size();i++)
            sum1+=A[i];
        for(int i = 0;i<B.size();i++)
            sum2+=B[i];
        int delta = (sum1-sum2)/2;
        vector<int>res;
        for(int i = 0;i<B.size();i++){
            int t = B[i] + delta;
            if(S.count(t)){// 查找t是否在A中
                res.push_back(t);
                res.push_back(B[i]);
                break;
            }
        }
        return res;
    }
};