LeetCode 力扣官方题解 | 888. 公平的糖果棒交换

力扣 888. 公平的糖果棒交换（点击查看题目）

题目描述

爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 根糖果棒的大小，B[j]是鲍勃拥有的第 j 根糖果棒的大小。

因为他们是朋友，所以他们想交换一根糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）

返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。

如果有多个答案，你可以返回其中任何一个。保证答案存在。

示例 1：

输入：A = [1,1], B = [2,2]输出：[1,2]

示例 2：

输入：A = [1,2], B = [2,3]输出：[1,2]

示例 3：

输入：A = [2], B = [1,3]输出：[2,3]

示例 4：

输入：A = [1,2,5], B = [2,4]输出：[5,4]

提示：

1 <= A.length <= 10000
1 <= B.length <= 10000
1 <= A[i] <= 100000
1 <= B[i] <= 100000
保证爱丽丝与鲍勃的糖果总量不同。
答案肯定存在。

解决方案

方法一：哈希表

思路及算法

记爱丽丝的糖果棒的总大小为 sumA，鲍勃的糖果棒的总大小为 sumB。设答案为 {x,y}，即爱丽丝的大小为 x 的糖果棒与鲍勃的大小为 y 的糖果棒交换，则有如下等式：

sumA - x + y = sumB + x - y

化简，得：

即对于 B 中的任意一个数 y'，只要 A 中存在一个数 x'，满足

，那么 {x',y'} 即为一组可行解。

为了快速查询 A 中是否存在某个数，我们可以先将 A 中的数字存入哈希表中。然后遍历 B 序列中的数 y'，在哈希表中查询是否有对应的 x'。

代码

C++

classSolution {public:vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {int sumA = accumulate(A.begin(), A.end(), 0);int sumB = accumulate(B.begin(), B.end(), 0);int delta = (sumA - sumB) / 2;unordered_set<int> rec(A.begin(), A.end());vector<int> ans;for (auto& y : B) {int x = y + delta;if (rec.count(x)) { ans = vector<int>{x, y};break; } }return ans; }};

Java

classSolution {publicint[] fairCandySwap(int[] A, int[] B) {int sumA = Arrays.stream(A).sum();int sumB = Arrays.stream(B).sum();int delta = (sumA - sumB) / 2; Set<Integer> rec = new HashSet<Integer>();for (int num : A) { rec.add(num); }int[] ans = newint[2];for (int y : B) {int x = y + delta;if (rec.contains(x)) { ans[0] = x; ans[1] = y;break; } }return ans; }}

JavaScript

var fairCandySwap = function(A, B) {const sumA = _.sum(A), sumB = _.sum(B);const delta = Math.floor((sumA - sumB) / 2);const rec = newSet(A);var ans;for (const y of B) {const x = y + delta;if (rec.has(x)) { ans = [x, y];break; } }return ans;};

Python3

classSolution:def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]: sumA, sumB = sum(A), sum(B) delta = (sumA - sumB) // 2 rec = set(A) ans = Nonefor y in B: x = y + deltaif x in rec: ans = [x, y]breakreturn ans

Golang

funcfairCandySwap(a, b []int) []int { sumA := 0 setA := map[int]struct{}{}for _, v := range a { sumA += v setA[v] = struct{}{} } sumB := 0for _, v := range b { sumB += v } delta := (sumA - sumB) / 2for i := 0; ; i++ { y := b[i] x := y + deltaif _, has := setA[x]; has {return []int{x, y} } }}

structHashTable {int x; UT_hash_handle hh;};int* fairCandySwap(int* A, int ASize, int* B, int BSize, int* returnSize){int sumA = 0, sumB = 0;for (int i = 0; i < ASize; i++) { sumA += A[i]; }for (int i = 0; i < BSize; i++) { sumB += B[i]; }int delta = (sumA - sumB) / 2;structHashTable* hashTable = NULL;for (int i = 0; i < ASize; i++) {structHashTable* tmp; HASH_FIND_INT(hashTable, &A[i], tmp);if (tmp == NULL) { tmp = malloc(sizeof(struct HashTable)); tmp->x = A[i]; HASH_ADD_INT(hashTable, x, tmp); } }int* ans = malloc(sizeof(int) * 2);for (int i = 0; i < BSize; i++) {int x = B[i] + delta;structHashTable* tmp; HASH_FIND_INT(hashTable, &x, tmp);if (tmp != NULL) { ans[0] = x, ans[1] = B[i]; *returnSize = 2;break; } }return ans;}

复杂度分析

时间复杂度：O(n + m)，其中 n 是序列 A 的长度，m 是序列 B 的长度。
空间复杂度：O(n)，其中 n 是序列 A 的长度。我们需要建立一个和序列 A 等大的哈希表。

BY /

本文作者：力扣

编辑&版式：霍霍