【题解】公平的糖果棒交换

题目来源：公平的糖果棒交换

思路及算法

记Alice的糖果棒的总大小为$sumA$，Bob的糖果棒的总大小为$sumB$。设答案为{x, y}，即Alice的大小为$x$的糖果棒与Bob的大小为$y$的糖果棒交换，则有如下等式：
$$
sumA-x+y = sumB+x-y
$$
化简，得：
$$
x = y+\frac{sumA-sumB}{2}
$$
对于$B$中的任意一个数$y‘$，只要$A$存在一个数$x‘$，满足$x‘=y‘+\frac{sumA-sumB}{2}$，那么{x‘, y‘}就是一组可行解。

首先我们将A中的数字存入哈希表中。然后遍历B序列中的数字，查看是否有对应的值即可。

class Solution{
    public int[] fairCandySwap(int[] A, int[] B){
        int sumA = Arrays.stream(A).sum();
        int sumB = Arrays.stream(B).sum();
        int delta = (sumA-sumB)/2;
        Set<Integer> rec = new HashSet<Integer>();
        for (int num : A) {
            rec.add(num);
        }
        int[] ans = new int[2];
        for (int y:B){
            int x = y + delta;
            if(rec.contains(x)){
                ans[0] = x;
                ans[1] = y;
                break;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n+m)$，其中$n$是序列$A$的长度，$m$是序列$B$的长度。
• 空间复杂度：$O(n)$，其中$n$是序列$A$的长度。我们需要建立一个和序列$A$等大的哈希表

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/fair-candy-swap/solution/gong-ping-de-tang-guo-jiao-huan-by-leetc-tlam/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

【题解】公平的糖果棒交换

原文：https://www.cnblogs.com/zzzzzy2k/p/14364570.html