公平的糖果交换

标签: 数组 哈希表 二分查找 排序

难度: Easy

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 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
  • 爱丽丝和鲍勃的糖果总数量不同。
  • 题目数据保证对于给定的输入至少存在一个有效答案。

Submission

运行时间: 55 ms

内存: 17.9 MB

class Solution:
    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
        sumA = sum(aliceSizes)
        sumB = sum(bobSizes)
        delta = (sumA - sumB) // 2
        setA = set(aliceSizes)
        for b in bobSizes:
            a = b + delta
            if a in setA:
                ans = [a, b]
                break

        return ans

Explain

题解的思路是通过找到一个公式来确定爱丽丝和鲍勃需要交换的糖果盒数量，使得交换后两人的糖果总量相等。首先计算出爱丽丝和鲍勃各自糖果的总数量sumA和sumB。通过计算delta = (sumA - sumB) / 2，得到爱丽丝需要比鲍勃多交换的糖果数量。通过遍历鲍勃的糖果数组，查找一个糖果数b，使得a = b + delta存在于爱丽丝的糖果集合中，即找到一个满足条件的(a, b)对，返回这个对即为答案。

时间复杂度: O(m + n)

空间复杂度: O(m)

class Solution:
    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
        sumA = sum(aliceSizes) # 爱丽丝的糖果总数
        sumB = sum(bobSizes) # 鲍勃的糖果总数
        delta = (sumA - sumB) // 2 # 计算需要交换的糖果数量差
        setA = set(aliceSizes) # 将爱丽丝的糖果数存入集合以便快速查找
        for b in bobSizes: # 遍历鲍勃的糖果数
            a = b + delta # 找到爱丽丝需要交换的糖果数
            if a in setA: # 如果这个糖果数在爱丽丝的集合中
                ans = [a, b] # 找到答案
                break
        return ans # 返回答案

Explore

这个计算逻辑基于平衡交换的原则。设交换后两人的糖果总量相等，因此有等式：sumA - a + b = sumB - b + a。整理得2a - 2b = sumA - sumB，即a - b = (sumA - sumB) / 2。这里的delta = (sumA - sumB) / 2表示爱丽丝和鲍勃在达到平衡状态时，糖果数差的一半，即爱丽丝需要额外给出的糖果数与鲍勃需要增加的糖果数之差。

选择遍历bobSizes主要是因为我们需要找到满足a = b + delta的对应关系，这里delta是通过sumA和sumB计算得到的固定值。通过先固定b，然后计算a = b + delta可以直接判断a是否存在于aliceSizes的集合中，这样的查找是O(1)的时间复杂度，使得整体算法效率为O(n)，其中n是bobSizes的长度。如果反过来遍历aliceSizes，对于每个a，我们需要计算b = a - delta并检查b是否在bobSizes中，这同样是高效的，因此遍历哪一个数组主要取决于实现细节和数组长度，没有根本性的效率差异。

如果aliceSizes和bobSizes中有重复的糖果数，不会影响算法的正确性或输出结果。算法寻找的是一对满足特定条件的(a, b)，即使有重复的糖果数，只要找到任意一对满足a = b + delta的糖果数对即可。算法只需返回找到的第一对满足条件的糖果对，因此重复的糖果数不会导致输出结果有错误或多余的对。

如果sumA和sumB的差是奇数，则使用整数除法//计算delta会导致结果向下取整，从而使delta不准确，因为a和b必须是整数。这种情况下，题解中的方法将无法找到正确的(a, b)对，因为不存在整数a和b满足a - b等于一个非整数。题目的描述中并没有明确保证sumA和sumB的差总是偶数，这是一个需要额外验证或者题目假设需要明确的地方。如果不保证这一点，算法需要额外的逻辑来处理这种情况或者在题目条件中明确说明。