力扣888 公平糖果交换

题目

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。 两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。 返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。 示例 1： 输入：aliceSizes = [1,1], bobSizes = [2,2] 输出：[1,2] 示例 2： 输入：aliceSizes = [1,2], bobSizes = [2,3] 输出：[1,2] 示例 3： 输入：aliceSizes = [2], bobSizes = [1,3] 输出：[2,3] 示例 4： 输入：aliceSizes = [1,2,5], bobSizes = [2,4] 输出：[5,4]

解决

这个问题可以通过数学推导来解决。假设爱丽丝的糖果总数为sumA，鲍勃的糖果总数为sumB。爱丽丝交换糖果x，鲍勃交换糖果y，则有以下两个等式：

sumA - x + y = sumB + x - y （爱丽丝交出糖果x并获得糖果y，鲍勃交出糖果y并获得糖果x）

sumA - x + y = sumB + x - y

从这两个等式可以得出：2 * (x - y) = sumA - sumB

因此，我们可以通过遍历aliceSizes和bobSizes，计算出sumA和sumB，然后求解上述等式，找到满足条件的x和y。

public class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int sumA = 0, sumB = 0;
        for (int size : aliceSizes) {
            sumA += size;
        }
        for (int size : bobSizes) {
            sumB += size;
        }
        
        int[] result = new int[2];
        for (int i = 0; i < aliceSizes.length; i++) {
            for (int j = 0; j < bobSizes.length; j++) {
                if (2 * (aliceSizes[i] - bobSizes[j]) == sumA - sumB) {
                    result[0] = aliceSizes[i];
                    result[1] = bobSizes[j];
                    return result;
                }
            }
        }
        return result;
    }
}