文章目录

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

题目

标题和出处

标题：公平的糖果交换

出处：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 ≤ 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]≤105Alice 和 Bob 的糖果总量不同给定的输入至少有一个有效的答案

解法

思路和算法

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

用 aliceSum \textit{aliceSum} aliceSum 和 bobSum \textit{bobSum} bobSum 分别表示 Alice 和 Bob 拥有的糖果总量，则根据题目描述可知， aliceSum − bobSum \textit{aliceSum} - \textit{bobSum} aliceSum−bobSum 是一个不为 0 0 0 的偶数。记 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 − bobSum 2 \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 的长度分别是 m m m 和 n n n。遍历数组 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 ( m n ) 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<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 ) O(m + n) O(m+n)，其中 m m m 和 n n n 分别是数组 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)，其中 n n n 是数组 bobSizes \textit{bobSizes} bobSizes 的长度。空间复杂度主要取决于哈希集合，哈希集合中的元素个数最多为 n n n。