解决方案


方法:方程求解

思路

如果爱丽丝交换糖果 x,她将会期待交换一些特定量的糖果 y 回来。

算法

设爱丽丝和鲍勃分别总计有 的糖果。

如果爱丽丝给了糖果 ,并且收到了糖果 ,那么鲍勃收到糖果 并给出糖果 。那么,我们一定有

对于公平的糖果交换。这意味着

我们的策略很简单。对于爱丽丝拥有的每个糖果 ,如果鲍勃有糖果 ,我们就返回 。我们在常量时间内使用集 Set 结构来检查Bob是否拥有所需的糖果

复杂度分析

  • 时间复杂度:

  • 空间复杂度:setB 用去的空间。(通过使用 if 语句,我们可以将其改进到 。)