888. 公平的糖果交换

🟢   🔖  数组 哈希表 二分查找 排序  🔗 力扣 LeetCode

题目

Alice and Bob have a different total number of candies. You are given two integer arrays aliceSizes and bobSizes where aliceSizes[i] is the number of candies of the ith box of candy that Alice has and bobSizes[j] is the number of candies of the jth box of candy that Bob has.

Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy. The total amount of candy a person has is the sum of the number of candies in each box they have.

Return a n integer arrayanswer whereanswer[0]is the number of candies in the box that Alice must exchange, andanswer[1]is the number of candies in the box that Bob must exchange. If there are multiple answers, you may return any one of them. It is guaranteed that at least one answer exists.

Example 1:

Input: aliceSizes = [1,1], bobSizes = [2,2]

Output: [1,2]

Example 2:

Input: aliceSizes = [1,2], bobSizes = [2,3]

Output: [1,2]

Example 3:

Input: aliceSizes = [2], bobSizes = [1,3]

Output: [2,3]

Constraints:

• 1 <= aliceSizes.length, bobSizes.length <= 10^4
• 1 <= aliceSizes[i], bobSizes[j] <= 10^5
• Alice and Bob have a different total number of candies.
• There will be at least one valid answer for the given input.

题目大意

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 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 <= 10^4
• 1 <= aliceSizes[i], bobSizes[j] <= 10^5
• 爱丽丝和鲍勃的糖果总数量不同。
• 题目数据保证对于给定的输入至少存在一个有效答案。

解题思路

1. 使用 reduce 函数计算爱丽丝和鲍勃各自拥有的糖果总数。记爱丽丝的总糖果数为 sumAlice，鲍勃的总糖果数为 sumBob。

2. 为了使两人的糖果数量相同，假设爱丽丝交换的是 x 盒糖果，鲍勃交换的是 y 盒糖果。要满足以下条件： sumAlice - x + y = sumBob + x - y 通过整理，得到： x - y = (sumAlice - sumBob) / 2

3. 使用集合查找交换的糖果：

   • 假设 target = (sumAlice - sumBob) / 2
   • 遍历爱丽丝的糖果盒数组，对于每个 aliceSizes 中 x，检查 y = x - target 是否在 bobSizes 中。
   • 如果是，说明爱丽丝和鲍勃可以交换 x 和 y 盒糖果，返回 [x, y]。
   • 使用 Set 存储鲍勃的糖果数量，这样可以在 O(1) 时间内检查是否存在符合条件的 y。

复杂度分析

• 时间复杂度：O(n + m)，其中 n 和 m 分别是 aliceSizes 和 bobSizes 的长度，需要遍历两个数组求和。
• 空间复杂度：O(m)，使用 Set 存储鲍勃的糖果数量。

代码

/**
 * @param {number[]} aliceSizes
 * @param {number[]} bobSizes
 * @return {number[]}
 */
var fairCandySwap = function (aliceSizes, bobSizes) {
	const sumAlice = aliceSizes.reduce((a, b) => a + b, 0);
	const sumBob = bobSizes.reduce((a, b) => a + b, 0);

	// 计算目标差值
	const target = (sumAlice - sumBob) / 2;

	// 使用 Set 存储鲍勃的糖果数量，便于查找
	const bobSet = new Set(bobSizes);

	for (let x of aliceSizes) {
		const y = x - target;
		if (bobSet.has(y)) {
			return [x, y]; // 返回交换的糖果数量
		}
	}
};