LeetCode 题解工作台
公平的糖果交换
爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ， aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量， bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。 两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量…
4
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以先计算出爱丽丝和鲍勃的糖果总数之差，除以二得到需要交换的糖果数之差 ，用一个哈希表 存储鲍勃的糖果盒中的糖果数，然后遍历爱丽丝的糖果盒，对于每个糖果数 ，我们判断 $\textit{a} - \textit{diff}$ 是否在哈希表 中，如果存在，说明找到了一组答案，返回即可。 时间复杂度 $O(m + n)$，空间复杂度 。其中 和 分别是爱丽丝和鲍勃的糖果盒的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 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 <= 1041 <= aliceSizes[i], bobSizes[j] <= 105- 爱丽丝和鲍勃的糖果总数量不同。
- 题目数据保证对于给定的输入至少存在一个有效答案。
解题思路
方法一：哈希表
我们可以先计算出爱丽丝和鲍勃的糖果总数之差，除以二得到需要交换的糖果数之差 ，用一个哈希表 存储鲍勃的糖果盒中的糖果数，然后遍历爱丽丝的糖果盒，对于每个糖果数 ，我们判断 是否在哈希表 中，如果存在，说明找到了一组答案，返回即可。
时间复杂度 ，空间复杂度 。其中 和 分别是爱丽丝和鲍勃的糖果盒的数量。
class Solution:
def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
diff = (sum(aliceSizes) - sum(bobSizes)) >> 1
s = set(bobSizes)
for a in aliceSizes:
if (b := (a - diff)) in s:
return [a, b]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m) due to summing arrays and iterating once over Alice's boxes with constant-time hash lookups. Space complexity is O(m) to store Bob's boxes in a hash set for fast membership checking. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you recognize the pattern of array scanning plus hash lookup.
- question_mark
Tests whether you handle differences in total sums correctly.
- question_mark
Looks for use of constant-time data structures to avoid nested loops.
常见陷阱
外企场景- error
Trying nested loops without using hash set, resulting in O(n*m) complexity.
- error
Miscomputing the delta by not dividing the total difference by 2.
- error
Returning invalid pairs or assuming multiple swaps are needed instead of exactly one.
进阶变体
外企场景- arrow_right_alt
Swapping multiple boxes to balance totals instead of just one.
- arrow_right_alt
Allowing unequal exchanges but minimizing difference after swap.
- arrow_right_alt
Input arrays with duplicate candy counts requiring handling in the hash set.