leetcode 888. 公平的糖果交换

leetcode 888. 公平的糖果交换

题目描述

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]

提示：

1 <= aliceSizes.length, bobSizes.length <= 104 1 <= aliceSizes[i], bobSizes[j] <= 105 爱丽丝和鲍勃的糖果总数量不同。 题目数据保证对于给定的输入至少存在一个有效答案。

解题思路

法1

方法1:模拟\

1. 遍历数组,计算两个人糖果的差值x(n1-n2)

2. 将第一列的糖果存入map[int]bool中,其中key代表糖果盒中糖果的数量,value表示是否有.就是改数量的糖果盒是否存在

3. 遍历第二人的糖果盒(y个糖果),在map中映射key为x+y的糖果盒是否存在,如果存在,则输出,不存在继续遍历

• 时间复杂度(O(n))
• 空间复杂度(O(n))

执行结果

法1

首先，计算爱丽丝和鲍勃拥有的糖果总数。使用两个变量 sumAlice 和 sumBob 分别保存两人的总数，并初始化为0。

然后，计算两人糖果数量的差值 diff，即 (sumAlice - sumBob) / 2。这是因为我们希望交换后两人的糖果总数相等，所以交换的差值应该是两人总数差的一半。

创建一个map bobSet，用来存储鲍勃拥有的糖果数量。

遍历爱丽丝的糖果数量 aliceSizes，对于每一个数量 size，判断是否存在 bobSet[size-diff]，即是否存在一个数量使得交换后两人的糖果总数相等。

如果找到匹配的数量，返回结果 [size, size-diff]，即爱丽丝需要交换的糖果数量和鲍勃需要交换的糖果数量。

如果遍历完所有的糖果数量仍然没有找到匹配的数量，返回 nil。

func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
    sumAlice := 0
    sumBob := 0

    // 计算爱丽丝和鲍勃拥有的糖果总数
    for _, size := range aliceSizes {
        sumAlice += size
    }
    for _, size := range bobSizes {
        sumBob += size
    }

    diff := (sumAlice - sumBob) / 2

    // 将鲍勃的糖果数量放入map中
    bobSet := make(map[int]bool)
    for _, size := range bobSizes {
        bobSet[size] = true
    }

    // 遍历爱丽丝的糖果数量，寻找匹配的糖果数量
    for _, size := range aliceSizes {
        if bobSet[size-diff] {
            return []int{size, size - diff}
        }
    }

    return nil
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 56 ms , 在所有 Go 提交中击败了 75.32% 的用户 内存消耗： 6.9 MB , 在所有 Go 提交中击败了 63.64% 的用户 通过测试用例： 75 / 75 炫耀一下: