【题解】力扣888.公平的糖果棒交换

题目来源

888.公平的糖果棒交换

思路及算法

记Alice的糖果棒的总大小为\(sumA\)，Bob的糖果棒的总大小为\(sumB\)。设答案为{x, y}，即Alice的大小为\(x\)的糖果棒与Bob的大小为\(y\)的糖果棒交换，则有如下等式：

化简，得：

对于\(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) {		// 遍历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\)等大的哈希表

参考资料：

1. 力扣官方题解：公平的糖果交换