0888. Fair Candy Swap #
题目 #
- 爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组
aliceSizes和bobSizes，aliceSizes[i]是爱丽丝拥有的第i盒糖果中的糖果数量，bobSizes[j]是鲍勃拥有的第j盒糖果中的糖果数量。 - 两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。
- 返回一个整数数组
answer，其中answer[0]是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1]是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。
思路 #
哈希 #
代码 #
哈希 #
class Solution {
public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
/** 设发生交换时，Alice和Bob拿出的糖果数量分别为x和y
* sumAlice - x + y = sumBob - y + x
* 成为两数之和问题
*/
int nAlice = 0, nBob = 0;
for (int num: aliceSizes) nAlice += num;
for (int num: bobSizes) nBob += num;
Set<Integer> set = new HashSet<>();
for (int num: aliceSizes) set.add(num);
for (int num: bobSizes) {
if (set.contains(num + (nAlice - nBob) / 2)) return new int[]{num + (nAlice - nBob) / 2, num};
}
return new int[2];
}
}