文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：公平的糖果交换

出处：888. 公平的糖果交换

难度

3 级

题目描述

要求

Alice 和 Bob 有不同数量的糖果。给你两个整数数组 $\text{aliceSizes}$ 和 $\text{bobSizes}$，其中 $\text{aliceSizes[i]}$ 是 Alice 拥有的第 $\text{i}$ 个糖果盒子中的糖果数量，$\text{bobSizes[j]}$ 是 Bob 拥有的第 $\text{j}$ 个糖果盒子中的糖果数量。

因为他们是朋友，所以他们想交换一个糖果盒子，使得交换后，他们都有相同的糖果总量。一个人拥有的糖果总量是他们拥有的糖果盒子中的糖果数量总和。

返回一个整数数组 $\text{answer}$，其中 $\text{answer[0]}$ 是 Alice 必须交换的糖果盒子中的糖果数量，$\text{answer[1]}$ 是 Bob 必须交换的糖果盒子中的糖果数量。如果有多个答案，你可以返回其中任何一个。保证至少有一个答案存在。

示例

示例 1：

输入：$\text{aliceSizes=[1,1],bobSizes=[2,2]}$
输出：$\text{[1,2]}$

示例 2：

输入：$\text{aliceSizes=[1,2],bobSizes=[2,3]}$
输出：$\text{[1,2]}$

示例 3：

输入：$\text{aliceSizes=[2],bobSizes=[1,3]}$
输出：$\text{[2,3]}$

示例 4：

输入：$\text{aliceSizes=[1,2,5],bobSizes=[2,4]}$
输出：$\text{[5,4]}$

数据范围

• 1 ≤ aliceSizes.length, bobSizes.length ≤ 10 4 \texttt{1} \le \texttt{aliceSizes.length, bobSizes.length} \le \texttt{10}^\texttt{4} 1≤aliceSizes.length,bobSizes.length≤104
• 1 ≤ aliceSizes[i], bobSizes[j] ≤ 10 5 \texttt{1} \le \texttt{aliceSizes[i], bobSizes[j]} \le \texttt{10}^\texttt{5} 1≤aliceSizes[i],bobSizes[j]≤105
• Alice 和 Bob 的糖果总量不同
• 给定的输入至少有一个有效的答案

解法

思路和算法

由于一定有答案，因此不需要判断答案是否存在，而是可以直接计算。

用 $\text{aliceSum}$ 和 $\text{bobSum}$ 分别表示 Alice 和 Bob 拥有的糖果总量，则根据题目描述可知，$\text{aliceSum}-\text{bobSum}$ 是一个不为 $0$ 的偶数。记 Alice 和 Bob 交换的糖果数量分别为 $\text{answer}[0]$ 和 $\text{answer}[1]$，则有 $\text{aliceSum}-\text{answer}[0]+\text{answer}[1]=\text{bobSum}-\text{answer}[1]+\text{answer}[0]$，整理得 $\text{aliceSum}-\text{bobSum}=2\times (\text{answer}[0]-\text{answer}[1])$。记 difference = aliceSum − bobSum 2 \textit{difference} = \dfrac{\textit{aliceSum} – \textit{bobSum}}{2} difference=2aliceSum−bobSum​，则有 $\text{answer}[0]-\text{answer}[1]=\text{difference}$。

对于数组 $\text{aliceSizes}$ 中的元素 $\text{size}$，如果在数组 $\text{bobSizes}$ 中存在元素 $\text{size}-\text{difference}$，则 $[\text{size},\text{size}-\text{difference}]$ 即为一个有效的答案。为了找到答案，需要遍历数组 $\text{aliceSizes}$，对于其中的每个元素 $\text{size}$ 判断数组 $\text{bobSizes}$ 中是否存在元素 $\text{size}-\text{difference}$。

假设数组 $\text{aliceSizes}$ 和 $\text{bobSizes}$ 的长度分别是 $m$ 和 $n$。遍历数组 $\text{aliceSizes}$ 需要 $O(m)$ 的时间，对于每个元素 $\text{size}$，如果直接遍历数组 $\text{bobSizes}$ 判断是否存在元素 $\text{size}-\text{difference}$，则每个元素需要 $O(n)$ 的时间，寻找答案时间复杂度是 $O(mn)$，需要优化。

为了降低时间复杂度，需要用哈希集合存储数组 $\text{bobSizes}$ 中的元素，在哈希集合中判断元素是否存在的时间是 $O(1)$，寻找答案的时间复杂度降至 $O(m)$。

由于在寻找答案之前需要遍历数组 $\text{bobSizes}$ 并将元素加入哈希集合，需要 $O(n)$ 的时间，因此总时间复杂度是 $O(m+n)$。

代码

class Solution {    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {        int aliceSum = Arrays.stream(aliceSizes).sum();        int bobSum = Arrays.stream(bobSizes).sum();        Set<Integer> bobSet = new HashSet<Integer>();        for (int size : bobSizes) {            bobSet.add(size);        }        int difference = (aliceSum - bobSum) / 2;        int[] answer = new int[2];        for (int size : aliceSizes) {            if (bobSet.contains(size - difference)) {                answer[0] = size;                answer[1] = size - difference;                break;            }        }        return answer;    }}

复杂度分析

• 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别是数组 $\text{aliceSizes}$ 和 $\text{bobSizes}$ 的长度。计算 Alice 和 Bob 拥有的糖果总量分别需要 $O(m)$ 和 $O(n)$ 的时间，将数组 $\text{bobSizes}$ 中的元素加入哈希集合需要 $O(n)$ 的时间，遍历数组 $\text{aliceSizes}$ 寻找答案需要 $O(m)$ 的时间，因此总时间复杂度是 $O(m+n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{bobSizes}$ 的长度。空间复杂度主要取决于哈希集合，哈希集合中的元素个数最多为 $n$。