酷客网力扣 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 <= 100001 <= B.length <= 100001 <= A[i] <= 1000001 <= 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++
class Solution {
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
class Solution {
public int[] 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 = new int[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 = new Set(A);
var ans;
for (const y of B) {
const x = y + delta;
if (rec.has(x)) {
ans = [x, y];
break;
}
}
return ans;
};
Python3
class Solution:
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 = None
for y in B:
x = y + delta
if x in rec:
ans = [x, y]
break
return ans
Golang
func fairCandySwap(a, b []int) []int {
sumA := 0
setA := map[int]struct{}{}
for _, v := range a {
sumA += v
setA[v] = struct{}{}
}
sumB := 0
for _, v := range b {
sumB += v
}
delta := (sumA - sumB) / 2
for i := 0; ; i++ {
y := b[i]
x := y + delta
if _, has := setA[x]; has {
return []int{x, y}
}
}
}
C
struct HashTable {
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;
struct HashTable* hashTable = NULL;
for (int i = 0; i < ASize; i++) {
struct HashTable* 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;
struct HashTable* 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 等大的哈希表。
酷客网相关文章：
评论前必须登录！
注册