看题和准备

今天介绍的是LeetCode算法题中Easy级别的第208题(顺位题号是888)。Alice和Bob有不同大小的糖果棒:A[i]是Alice拥有的第i个糖果棒的大小,B[j]是Bob拥有的第j个糖果棒的大小。

由于他们是朋友,他们想交换一个糖果,以便交换后,他们都有相同的糖果总量。 (一个人拥有的糖果总量是他们拥有的糖果大小的总和。)

返回一个整数数组ans,其中ans[0]是Alice必须交换的糖果的大小,ans[1]是Bob必须交换的糖果的大小。

如果有多个答案,你可以返回其中任何一个。答案保证存在。例如:

输入:A = [1,1],B = [2,2]
输出:[1,2]

输入:A = [1,2],B = [2,3]
输出:[1,2] [2,3]

输入:A = [2],B = [1,3]
输出:[2,3]

输入:A = [1,2,5],B = [2,4]
输出:[5,4]

注意:

1 <= A.length <= 10000

1 <= B.length <= 10000

1 <= A [i] <= 100000

1 <= B [i] <= 100000

保证Alice和Bob的糖果总量不同。

保证有答案。

第一种解法

Alice和Bob的糖果总量不一样,要想答案肯定存在,他们两人的糖果总量差值肯定为偶数,只有差值为偶数时,对差值进行平分得到一个平均值,糖果总量多的一方减去平均值,少的一方加上平均值,此时两人的糖果总量是相等的。

因此,我们只需要求出两人的糖果总量差值的平均数,拿此平均数加上一方中的任意一个糖果的大小,去匹配另外一方中的糖果大小,能够匹配上,说明这两个糖果是需要双方交换的,在此情景下,此题有点类似于Two Sum。

    public int[] fairCandySwap(int[] A, int[] B) {
        // 存储A中的元素(换成B也行)
        Set<Integer> set = new HashSet<>();
        int[] result = new int[2];
        int sumA = 0;
        for (int a : A) {
            sumA += a;
            set.add(a);
        }
        int sumB = 0;
        for (int b : B) {
            sumB += b;
        }
        // 两人糖果总量之差的平均数
        int num = (sumA - sumB) / 2;
        // 遍历B中元素,加上差值平均数去另外一个数组里匹配,
        // 能匹配上,表明遇到了需要交换的元素。
        for (int b : B) {
            if (set.contains(b + num)) {
                return new int[]{b + num, b};
            }
        }
        return result;
    }

第二种解法

针对第一种解法使用的HashSet,我们还可以换成另外的数据结构来代替,使用一个boolean类型的数组来存储A中的值,其他思路不变。

public int[] fairCandySwap(int[] A, int[] B) {
        int[] result = new int[2];
        boolean[] set = new boolean[100001];
        int sumA = 0;
        for (int a : A) {
            sumA += a;
            set[a] = true;
        }
        int sumB = 0;
        for (int b : B) {
            sumB += b;
        }
        int num = (sumA - sumB) / 2;
        for (int b : B) {
            if (b + num > 0 && b + num < 100001 && set[b + num]) {
                return new int[]{b + num, b};
            }
        }
        return result;
    }