888. 公平的糖果棒交换

Easy

题目描述

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个整数数组 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]

提示：

1 <= aliceSizes.length, bobSizes.length <= 10^4
1 <= aliceSizes[i], bobSizes[j] <= 10^5
爱丽丝和鲍勃的糖果总数量不同
题目数据保证对于给定的输入至少存在一个有效答案

解题思路

这道题需要找到两个人各自交换一盒糖果后，使得双方糖果总数相等的方案。

首先分析数学关系：设爱丽丝总糖果数为 sumA，鲍勃总糖果数为 sumB。如果爱丽丝交换糖果数为 x，鲍勃交换糖果数为 y，那么交换后：

爱丽丝：sumA - x + y
鲍勃：sumB - y + x

要使两人糖果数相等：sumA - x + y = sumB - y + x 化简得：y = x + (sumB - sumA) / 2

因此，我们需要找到爱丽丝的某个糖果盒 x 和鲍勃的某个糖果盒 y，使得上述等式成立。

解法一：哈希表（推荐） 先计算两人糖果总数差值的一半，然后遍历爱丽丝的糖果盒，对每个糖果盒计算需要交换的鲍勃糖果盒大小，在哈希表中查找是否存在。

解法二：排序 + 双指针 对两个数组排序后，使用双指针技巧寻找满足条件的组合。

解法三：暴力搜索 双重循环遍历所有可能的交换组合，时间复杂度较高。

这里给出最优的哈希表解法，时间复杂度 O(m+n)，空间复杂度 O(n)。

代码实现

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
        int sumA = 0, sumB = 0;
        for (int candy : aliceSizes) sumA += candy;
        for (int candy : bobSizes) sumB += candy;
        
        int delta = (sumB - sumA) / 2;
        
        unordered_set<int> bobSet(bobSizes.begin(), bobSizes.end());
        
        for (int x : aliceSizes) {
            int y = x + delta;
            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)
        delta = (sum_b - sum_a) // 2
        
        bob_set = set(bobSizes)
        
        for x in aliceSizes:
            y = x + delta
            if y in bob_set:
                return [x, y]
        
        return []

public class Solution {
    public int[] FairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int sumA = aliceSizes.Sum();
        int sumB = bobSizes.Sum();
        int delta = (sumB - sumA) / 2;
        
        HashSet<int> bobSet = new HashSet<int>(bobSizes);
        
        foreach (int x in aliceSizes) {
            int y = x + delta;
            if (bobSet.Contains(y)) {
                return new int[] {x, y};
            }
        }
        
        return new int[0];
    }
}

var fairCandySwap = function(aliceSizes, bobSizes) {
    const sumA = aliceSizes.reduce((sum, candy) => sum + candy, 0);
    const sumB = bobSizes.reduce((sum, candy) => sum + candy, 0);
    const delta = (sumB - sumA) / 2;
    
    const bobSet = new Set(bobSizes);
    
    for (const x of aliceSizes) {
        const y = x + delta;
        if (bobSet.has(y)) {
            return [x, y];
        }
    }
    
    return [];
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

解法	时间复杂度	空间复杂度
哈希表	O(m + n)	O(n)
排序 + 双指针	O(m log m + n log n)	O(1)
暴力搜索	O(m × n)	O(1)

其中 m 和 n 分别为 aliceSizes 和 bobSizes 的长度。推荐使用哈希表解法，具有最优的时间复杂度。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析