英文原文
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 an integer array answer where answer[0] is the number of candies in the box that Alice must exchange, and answer[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]
Example 4:
Input: aliceSizes = [1,2,5], bobSizes = [2,4] Output: [5,4]
Constraints:
1 <= aliceSizes.length, bobSizes.length <= 1041 <= aliceSizes[i], bobSizes[j] <= 105- 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 <= 1041 <= aliceSizes[i], bobSizes[j] <= 105- 爱丽丝和鲍勃的糖果总数量不同。
- 题目数据保证对于给定的输入至少存在一个有效答案。
通过代码
高赞题解
方法一：哈希表
思路及算法
记爱丽丝的糖果棒的总大小为 $\textit{sumA}$，鲍勃的糖果棒的总大小为 $\textit{sumB}$。设答案为 ${x,y}$，即爱丽丝的大小为 $x$ 的糖果棒与鲍勃的大小为 $y$ 的糖果棒交换，则有如下等式：
$$
\textit{sumA} - x + y = \textit{sumB} + x - y
$$
化简，得：
$$
x = y + \frac{\textit{sumA} - \textit{sumB}}{2}
$$
即对于 $\textit{bobSizes}$ 中的任意一个数 $y’$，只要 $\textit{aliceSizes}$ 中存在一个数 $x’$，满足 $x’ = y’ + \dfrac{\textit{sumA} - \textit{sumB}}{2}$，那么 ${x’,y’}$ 即为一组可行解。
为了快速查询 $\textit{aliceSizes}$ 中是否存在某个数，我们可以先将 $\textit{aliceSizes}$ 中的数字存入哈希表中。然后遍历 $\textit{bobSizes}$ 序列中的数 $y’$，在哈希表中查询是否有对应的 $x’$。
代码
[sol1-C++]class Solution { public: vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) { int sumA = accumulate(aliceSizes.begin(), aliceSizes.end(), 0); int sumB = accumulate(bobSizes.begin(), bobSizes.end(), 0); int delta = (sumA - sumB) / 2; unordered_set<int> rec(aliceSizes.begin(), aliceSizes.end()); vector<int> ans; for (auto& y : bobSizes) { int x = y + delta; if (rec.count(x)) { ans = vector<int>{x, y}; break; } } return ans; } };
[sol1-Java]class Solution { public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) { int sumA = Arrays.stream(aliceSizes).sum(); int sumB = Arrays.stream(bobSizes).sum(); int delta = (sumA - sumB) / 2; Set<Integer> rec = new HashSet<Integer>(); for (int num : aliceSizes) { rec.add(num); } int[] ans = new int[2]; for (int y : bobSizes) { int x = y + delta; if (rec.contains(x)) { ans[0] = x; ans[1] = y; break; } } return ans; } }
[sol1-JavaScript]var fairCandySwap = function(aliceSizes, bobSizes) { const sumA = _.sum(aliceSizes), sumB = _.sum(bobSizes); const delta = Math.floor((sumA - sumB) / 2); const rec = new Set(aliceSizes); var ans; for (const y of bobSizes) { const x = y + delta; if (rec.has(x)) { ans = [x, y]; break; } } return ans; };
[sol1-Python3]class Solution: def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]: sumA, sumB = sum(aliceSizes), sum(bobSizes) delta = (sumA - sumB) // 2 rec = set(aliceSizes) ans = None for y in bobSizes: x = y + delta if x in rec: ans = [x, y] break return ans
[sol1-Golang]func fairCandySwap(aliceSizes []int, bobSizes []int) []int { sumA := 0 setA := map[int]struct{}{} for _, v := range aliceSizes { sumA += v setA[v] = struct{}{} } sumB := 0 for _, v := range bobSizes { sumB += v } delta := (sumA - sumB) / 2 for i := 0; ; i++ { y := bobSizes[i] x := y + delta if _, has := setA[x]; has { return []int{x, y} } } }
[sol1-C]struct HashTable { int x; UT_hash_handle hh; }; int* fairCandySwap(int* aliceSizes, int aliceSizesSize, int* bobSizes, int bobSizesSize, int* returnSize) { int sumA = 0, sumB = 0; for (int i = 0; i < aliceSizesSize; i++) { sumA += aliceSizes[i]; } for (int i = 0; i < bobSizesSize; i++) { sumB += bobSizes[i]; } int delta = (sumA - sumB) / 2; struct HashTable* hashTable = NULL; for (int i = 0; i < aliceSizesSize; i++) { struct HashTable* tmp; HASH_FIND_INT(hashTable, &aliceSizes[i], tmp); if (tmp == NULL) { tmp = malloc(sizeof(struct HashTable)); tmp->x = aliceSizes[i]; HASH_ADD_INT(hashTable, x, tmp); } } int* ans = malloc(sizeof(int) * 2); for (int i = 0; i < bobSizesSize; i++) { int x = bobSizes[i] + delta; struct HashTable* tmp; HASH_FIND_INT(hashTable, &x, tmp); if (tmp != NULL) { ans[0] = x, ans[1] = bobSizes[i]; *returnSize = 2; break; } } return ans; }
复杂度分析
时间复杂度：$O(n + m)$，其中 $n$ 是序列 $\textit{aliceSizes}$ 的长度，$m$ 是序列 $\textit{bobSizes}$ 的长度。
空间复杂度：$O(n)$，其中 $n$ 是序列 $\textit{aliceSizes}$ 的长度。我们需要建立一个和序列 $\textit{aliceSizes}$ 等大的哈希表。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 55755 | 87025 | 64.1% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
