LeetCode 888: Fair Candy Swap (Sum Difference + Hash Lookup)
LeetCode 888Hash SetMathToday we solve LeetCode 888 - Fair Candy Swap.
Source: https://leetcode.com/problems/fair-candy-swap/
English
Problem Summary
Alice has candy sizes in aliceSizes, Bob has bobSizes. They each swap one candy so that their total candy amounts become equal. Return any valid pair [x, y] where Alice gives x and Bob gives y.
Key Insight
Let sumA and sumB be total candies. After swapping x and y:
sumA - x + y = sumB - y + x
So x - y = (sumA - sumB) / 2. If we know x, then y = x - diff where diff = (sumA - sumB) / 2. Use a hash set for Bob’s values for O(1) lookup.
Algorithm
- Compute sumA and sumB.
- Compute diff = (sumA - sumB) / 2.
- Put all Bob candy sizes into a hash set.
- For each x in Alice, check whether x - diff exists in Bob’s set.
- Return the first valid pair [x, x - diff].
Complexity Analysis
Let n = len(aliceSizes), m = len(bobSizes).
Time: O(n + m).
Space: O(m).
Common Pitfalls
- Mixing formula direction: it is y = x - diff, not x + diff.
- Forgetting integer division assumption from problem guarantee.
- Using nested loops and getting O(nm) unnecessarily.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
int sumA = 0, sumB = 0;
for (int x : aliceSizes) sumA += x;
Set<Integer> bobSet = new HashSet<>();
for (int y : bobSizes) {
sumB += y;
bobSet.add(y);
}
int diff = (sumA - sumB) / 2;
for (int x : aliceSizes) {
int y = x - diff;
if (bobSet.contains(y)) {
return new int[]{x, y};
}
}
return new int[0];
}
}func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
sumA, sumB := 0, 0
for _, x := range aliceSizes {
sumA += x
}
bobSet := make(map[int]bool, len(bobSizes))
for _, y := range bobSizes {
sumB += y
bobSet[y] = true
}
diff := (sumA - sumB) / 2
for _, x := range aliceSizes {
y := x - diff
if bobSet[y] {
return []int{x, y}
}
}
return []int{}
}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);
unordered_set<int> bobSet(bobSizes.begin(), bobSizes.end());
int diff = (sumA - sumB) / 2;
for (int x : aliceSizes) {
int y = x - diff;
if (bobSet.count(y)) {
return {x, y};
}
}
return {};
}
};class Solution:
def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
sum_a = sum(aliceSizes)
sum_b = sum(bobSizes)
diff = (sum_a - sum_b) // 2
bob_set = set(bobSizes)
for x in aliceSizes:
y = x - diff
if y in bob_set:
return [x, y]
return []var fairCandySwap = function(aliceSizes, bobSizes) {
let sumA = 0, sumB = 0;
for (const x of aliceSizes) sumA += x;
const bobSet = new Set();
for (const y of bobSizes) {
sumB += y;
bobSet.add(y);
}
const diff = (sumA - sumB) / 2;
for (const x of aliceSizes) {
const y = x - diff;
if (bobSet.has(y)) {
return [x, y];
}
}
return [];
};中文
题目概述
Alice 的糖果数组是 aliceSizes，Bob 的是 bobSizes。两人各交换一块糖，使得交换后总和相等，返回任意可行答案 [x, y]（Alice 给出 x，Bob 给出 y）。
核心思路
设总和分别为 sumA、sumB。交换后满足：
sumA - x + y = sumB - y + x
化简得 x - y = (sumA - sumB) / 2。
因此对每个 Alice 的 x，只需检查 Bob 是否存在 y = x - diff，其中 diff = (sumA - sumB) / 2。用哈希集合可快速判断。
算法步骤
- 计算 sumA 与 sumB。
- 计算 diff = (sumA - sumB) / 2。
- 将 Bob 的糖果值放入哈希集合。
- 遍历 Alice 的每个 x，令 y = x - diff。
- 若 y 在 Bob 集合中，返回 [x, y]。
复杂度分析
设 n = len(aliceSizes)，m = len(bobSizes)。
时间复杂度：O(n + m)。
空间复杂度：O(m)。
常见陷阱
- 公式方向写反：应为 y = x - diff。
- 忽略题目保证导致的整除前提。
- 用双重循环暴力匹配，退化为 O(nm)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
int sumA = 0, sumB = 0;
for (int x : aliceSizes) sumA += x;
Set<Integer> bobSet = new HashSet<>();
for (int y : bobSizes) {
sumB += y;
bobSet.add(y);
}
int diff = (sumA - sumB) / 2;
for (int x : aliceSizes) {
int y = x - diff;
if (bobSet.contains(y)) {
return new int[]{x, y};
}
}
return new int[0];
}
}func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
sumA, sumB := 0, 0
for _, x := range aliceSizes {
sumA += x
}
bobSet := make(map[int]bool, len(bobSizes))
for _, y := range bobSizes {
sumB += y
bobSet[y] = true
}
diff := (sumA - sumB) / 2
for _, x := range aliceSizes {
y := x - diff
if bobSet[y] {
return []int{x, y}
}
}
return []int{}
}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);
unordered_set<int> bobSet(bobSizes.begin(), bobSizes.end());
int diff = (sumA - sumB) / 2;
for (int x : aliceSizes) {
int y = x - diff;
if (bobSet.count(y)) {
return {x, y};
}
}
return {};
}
};class Solution:
def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
sum_a = sum(aliceSizes)
sum_b = sum(bobSizes)
diff = (sum_a - sum_b) // 2
bob_set = set(bobSizes)
for x in aliceSizes:
y = x - diff
if y in bob_set:
return [x, y]
return []var fairCandySwap = function(aliceSizes, bobSizes) {
let sumA = 0, sumB = 0;
for (const x of aliceSizes) sumA += x;
const bobSet = new Set();
for (const y of bobSizes) {
sumB += y;
bobSet.add(y);
}
const diff = (sumA - sumB) / 2;
for (const x of aliceSizes) {
const y = x - diff;
if (bobSet.has(y)) {
return [x, y];
}
}
return [];
};
Comments