一 🏠 题目描述
888. 公平的糖果交换
爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 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]
示例 4：
输入：aliceSizes = [1,2,5], bobSizes = [2,4] 输出：[5,4]
提示：
1 <= aliceSizes.length, bobSizes.length <=1041 <= aliceSizes[i], bobSizes[j] <=105
爱丽丝和鲍勃的糖果总数量不同
题目数据保证对于给定的输入至少存在一个有效答案
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎
互相交换一盒糖果，拥有相同总数量的糖果，即伪代码如下 🌺🌺🌺
sum1 = count(aliceSizes) , sum2 = count(bobSizes) //两人糖果总数量 sum1 - aliceSizes[x] + bobSizes[y] = sum2 - bobSizes[y] + aliceSizes[x] //交换后等式成立
提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃
2.2 🚀 思路整理
哈希表法：把上述等式转换得 bobSizes[y] = ( sum2 - sum1 + 2 * aliceSizes[x] ) / 2 ，易知可使用哈希表法先将 bobSizes 中的数字存入哈希表， 提升查询效率（方法一） 🌷🌷🌷
双指针法：虽不及哈希表法，但还算巧妙，为开阔思维单列出
首先对 aliceSizes 和 bobSizes 进行排序，定义双指针 i ，j 和 target = (sum1 - sum2) / 2 ，双指针分别从已排序的 aliceSizes 和 bobSizes 左端开始移动 🐌🐌🐌
若 aliceSizes[i] - bobSizes[j] 小于 target ，说明 aliceSizes[i] 小了，++i 若 aliceSizes[i] - bobSizes[j] 大于 target ，说明 bobSizes[j] 小了，++j 若 aliceSizes[i] - bobSizes[j] 等于 target ，则说明等式成立，返回结果 🐳🐳🐳
整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) { //哈希表法 int sumA = accumulate(aliceSizes.begin(), aliceSizes.end(), 0); //求和糖果总数量 int sumB = accumulate(bobSizes.begin(), bobSizes.end(), 0); //求和糖果总数量 int delta = (sumA - sumB) / 2; //先计算出等式成立的定值 unordered_set<int> rec(aliceSizes.begin(), aliceSizes.end()); //将aliceSizes放入set for (auto& y : bobSizes) { //遍历 bobSizes int x = y + delta; //求出满足等式的 aliceSizes 元素值 if (rec.count(x)) { //若存在于 aliceSizes return{ x, y }; //返回结果 } } return {}; //返回结果 }
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) { //双指针法 int sum1 = accumulate(aliceSizes.cbegin(), aliceSizes.cend(), 0); //求和糖果总数量 int sum2 = accumulate(bobSizes.cbegin(), bobSizes.cend(), 0); //求和糖果总数量 std::sort(aliceSizes.begin(), aliceSizes.end()); //排序 std::sort(bobSizes.begin(), bobSizes.end()); //排序 int target = (sum1 - sum2) / 2; //计算出等式成立的定值 int i =0, j =0; //定义双指针 int len1 = aliceSizes.size(), len2 = bobSizes.size(); //获取数组长度 while (i != len1 && j != len2) { //均从左端开始遍历 int curr = aliceSizes[i] - bobSizes[j]; //计算当前值与等式成立定值比较 if (curr == target) return{ aliceSizes[i], bobSizes[j] }; //返回结果 elseif (curr > target) ++j; //说明 bobSizes[j] 小了 else++i; //说明 aliceSizes[i] 小了 } return{}; //返回结果 }
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇
unordered_set<int> rec(aliceSizes.begin(), aliceSizes.end()); //将aliceSizes放入set
这里与常规哈希表法不同之处在于，该题不需要对数组各元素计数，而只关心 aliceSizes 值。与哈希表相比，它和数组间转换逻辑更简洁，且 count 方法同样好用 🌼🌼🌼
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息并没有问题，在第二阶段 🚀 思路整理中联想到使用哈希表法，未联想到双指针法。但对于实现哈希表法的想法层面，挨个置入哈希表感觉太呆了（未联想到使用 set 解决该问题 😭😭😭）
所以博主的这道题也是在阅读完官方解析后，解出来并加以记录的
