LC 888. 公平的糖果棒交换
题目描述
这是 LeetCode 上的 888. 公平的糖果棒交换 ，难度为 简单。
爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 根糖果棒的大小，B[j] 是鲍勃拥有的第 j 根糖果棒的大小。
因为他们是朋友，所以他们想交换一根糖果棒，这样交换后，他们都有相同的糖果总量（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和）。
返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是鲍勃必须交换的糖果棒的大小。
如果有多个答案，你可以返回其中任何一个。
保证答案存在。
示例 1：1
2
3输入：A = [1,1], B = [2,2]
输出：[1,2]
示例 2：1
2
3输入：A = [1,2], B = [2,3]
输出：[1,2]
示例 3：1
2
3输入：A = [2], B = [1,3]
输出：[2,3]
示例 4：1
2
3输入：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$
- 保证爱丽丝与鲍勃的糖果总量不同
- 答案肯定存在
朴素解法
最终目的是让两个数组总和相等。
我们可以先分别求得两个数组总和为 aSum 和 bSum。
即有数组总和 total = aSum + bSum。
同时得数组目标总和 target = total / 2。
当前两个数组与目标总和的差值分别为 target - aSum 和 target - bSum。
我们记 diff = target - aSum。
对于某个 a[i] 而言，如果 a[i] 能构成答案，那么 b 数组中必然存在大小为 a[i] + diff 的值，使得两者交换后，数组总和均为 target。
因此我们只需要遍历数组 a，查找哪一个 a[i] 使得 a[i] + diff 存在于数组 b 即可。
Java 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public int[] fairCandySwap(int[] a, int[] b) {
int aSum = 0, bSum = 0;
for (int i : a) aSum += i;
for (int i : b) bSum += i;
int total = aSum + bSum, target = total / 2;
int diff = target - aSum;
for (int i : a) {
if (find(b, i + diff)) return new int[]{i, i + diff};
}
return null; // never
}
boolean find(int[] nums, int target) {
for (int i : nums) {
if (i == target) return true;
}
return false;
}
}
C++ 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
vector<int> fairCandySwap(vector<int>& a, vector<int>& b) {
int aSum = 0, bSum = 0;
for (int i : a) aSum += i;
for (int i : b) bSum += i;
int total = aSum + bSum, target = total / 2;
int diff = target - aSum;
vector<int> ans(2);
for (int i : a) {
if (find(b, i + diff)) {
ans[0] = i;
ans[1] = i + diff;
break;
}
}
return ans;
}
bool find(vector<int>& nums, int target) {
for (int i : nums) {
if (i == target) return true;
}
return false;
}
};
Python 代码：1
2
3
4
5
6
7
8
9
10class Solution:
def fairCandySwap(self, a: List[int], b: List[int]) -> List[int]:
aSum, bSum = sum(a), sum(b)
total = aSum + bSum
target = total // 2
diff = target - aSum
for i in a:
if i + diff in b:
return [i, i + diff]
return None
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function fairCandySwap(a: number[], b: number[]): number[] {
let aSum = a.reduce((acc, val) => acc + val, 0);
let bSum = b.reduce((acc, val) => acc + val, 0);
let total = aSum + bSum;
let target = Math.floor(total / 2);
let diff = target - aSum;
let ans: number[] = [];
for (let i of a) {
if (b.includes(i + diff)) {
ans = [i, i + diff];
break;
}
}
return ans;
};
- 时间复杂度： 计算总和复杂度为 $O(n)$，找到最终解复杂度为 $O(n^2)$。整体复杂度为 $O(n^2)$
- 空间复杂度：$O(1)$
查找优化
上述解法之所以无法做到线性，是因为我们每次都要对数组 b 进行扫描，确定 a[i] + diff 是否存在。
我们知道 map/set/数组 都可以实现 $O(1)$ 查找，由于这里明确给出了两个数组中出现的数的范围，因此可以使用数组进行计数。
同时可以优化一下变量的使用，使用一个变量 diff 来计算最终的差异值。
这种优化，是典型的空间换时间做法。
Java 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public int[] fairCandySwap(int[] a, int[] b) {
// 先求得 a 的总和
int diff = 0;
for (int i : a) diff += i;
// 使用 cnt 统计 b 中的数的出现次数，同时计算 a 总和与 b 总和的差值
int[] cnt = new int[100009];
for (int i : b) {
diff -= i;
cnt[i]++;
}
// 计算出 a 中具体的替换差值是多少
diff /= -2;
int[] ans = new int[2];
for (int i : a) {
int target = i + diff;
// 如果目标替换量在合法范围，并且存在于 b 数组中。说明找到解了
if (target >= 1 && target <= 100000 && cnt[target] > 0) {
ans[0] = i;
ans[1] = target;
break;
}
}
return ans;
}
}
C++ 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public:
vector<int> fairCandySwap(vector<int>& a, vector<int>& b) {
// 先求得 a 的总和
int diff = 0;
for (int i : a) diff += i;
// 使用 cnt 统计 b 中的数的出现次数，同时计算 a 总和与 b 总和的差值
vector<int> cnt(100009, 0);
for (int i : b) {
diff -= i;
cnt[i]++;
}
// 计算出 a 中具体的替换差值是多少
diff /= -2;
vector<int> ans(2);
for (int i : a) {
int target = i + diff;
// 如果目标替换量在合法范围，并且存在于 b 数组中。说明找到解了
if (target >= 1 && target <= 100000 && cnt[target] > 0) {
ans[0] = i;
ans[1] = target;
break;
}
}
return ans;
}
};
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution:
def fairCandySwap(self, a: List[int], b: List[int]) -> List[int]:
# 先求得 a 的总和
diff = sum(a)
# 使用 cnt 统计 b 中的数的出现次数，同时计算 a 总和与 b 总和的差值
cnt = [0] * 100009
for i in b:
diff -= i
cnt[i] += 1
# 计算出 a 中具体的替换差值是多少
diff //= -2
for i in a:
target = i + diff
# 如果目标替换量在合法范围，并且存在于 b 数组中。说明找到解了
if 1 <= target <= 100000 and cnt[target] > 0:
return [i, target]
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function fairCandySwap(a: number[], b: number[]): number[] {
// 先求得 a 的总和
let diff = a.reduce((acc, curr) => acc + curr, 0);
// 使用 cnt 统计 b 中的数的出现次数，同时计算 a 总和与 b 总和的差值
let cnt: number[] = new Array(100009).fill(0);
for (let i of b) {
diff -= i;
cnt[i]++;
}
// 计算出 a 中具体的替换差值是多少
diff = Math.floor(diff / -2);
for (let i of a) {
let target = i + diff;
// 如果目标替换量在合法范围，并且存在于 b 数组中。说明找到解了
if (target >= 1 && target <= 100000 && cnt[target] > 0) {
return [i, target];
}
}
return [];
}
- 时间复杂度：计算总和复杂度为 $O(n)$，找到最终解复杂度为 $O(n)$。整体复杂度为 $O(n)$
- 空间复杂度：使用
cnt数组进行计数。复杂度为 $O(n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.888 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
