这是悦乐书的第339次更新,第363篇原创

01 看题和准备

今天介绍的是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的糖果总量不同。

  • 保证有答案。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

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

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

public int[] fairCandySwap(int[] A, int[] B) {
    int[] result = new int[2];
    // 存储A中的元素(换成B也行)
    Set<Integer> set = new HashSet<Integer>();
    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;
}


03 第二种解法

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

public int[] fairCandySwap2(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;
}


04 小结

算法专题目前已连续日更超过六个月,算法题文章208+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!