文章目录

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

题目

标题和出处

标题：公平的糖果交换

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

难度

3 级

题目描述

要求

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

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

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

数据范围

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

解法

思路和算法

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

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

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

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

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

由于在寻找答案之前需要遍历数组 bobSizes\textit{bobSizes}bobSizes 并将元素加入哈希集合，需要 O(n)O(n)O(n) 的时间，因此总时间复杂度是 O(m+n)O(m + 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 bobSet = new HashSet();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)O(m + n)O(m+n)，其中 mmm 和 nnn 分别是数组 aliceSizes\textit{aliceSizes}aliceSizes 和 bobSizes\textit{bobSizes}bobSizes 的长度。计算 Alice 和 Bob 拥有的糖果总量分别需要 O(m)O(m)O(m) 和 O(n)O(n)O(n) 的时间，将数组 bobSizes\textit{bobSizes}bobSizes 中的元素加入哈希集合需要 O(n)O(n)O(n) 的时间，遍历数组 aliceSizes\textit{aliceSizes}aliceSizes 寻找答案需要 O(m)O(m)O(m) 的时间，因此总时间复杂度是 O(m+n)O(m + n)O(m+n)。

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