888. 公平的糖果棒交换
一、题目
爱丽丝和鲍勃有不同大小的糖果棒:A[i]
是爱丽丝拥有的第 i
根糖果棒的大小,B[j]
是鲍勃拥有的第 j
根糖果棒的大小。
因为他们是朋友,所以他们想交换一根糖果棒,这样交换后,他们都有相同的糖果总量。(一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。)
返回一个整数数组 ans
,其中 ans[0]
是爱丽丝必须交换的糖果棒的大小,ans[1]
是 Bob 必须交换的糖果棒的大小。
示例1:
1 | 输入:A = [1,1], B = [2,2] |
示例2:
1 | 输入:A = [1,2], B = [2,3] |
示例3:
1 | 输入:A = [2], B = [1,3] |
示例4:
1 | 输入:A = [1,2,5], B = [2,4] |
提示:
1 ≤ A.length ≤ 10000
1 ≤ B.length ≤ 10000
1 ≤ A[i] ≤ 100000
1 ≤ B[i] ≤ 100000
- 保证爱丽丝与鲍勃的糖果总量不同。
- 答案肯定存在。
二、题解
哈希表
思路如下:
这是一个纯数学问题,我们来把它数学化:
假设我们最后得结果是 $[a, b]$,也就是 $a$ 是 $A$ 要交换得,$b$ 是 $B$ 要交换的
我们可以计算分别得到 $A$ 和 $B$ 的和为 $aSum$ 和 $bSum$,那我们会有如下关系:
转化一下可以得到:
其实问题就是:对于 $B$ 中的任一数 $b$,在 $A$ 中存在一个数 $a$,满足上述关系式。
- 时间复杂度:$O(n+m)$,$n$ 和 $m$ 分别为 $A$ 和 $B$ 的长度。
- 空间复杂度:$O(n)$。
1 | var fairCandySwap = function (A, B) { |